You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I ran a quicksort killer like the one described in #178 with the following algorithms from the library - the ones that have a quicksort-like structure:
quick_sort
pdq_sort
quick_merge_sort (both the bidirectional rand random-access iterators versions)
Here are the results:
It is quite easy to see the difference between the O(n log n) and the O(n²) algorithms there. And it clearly shows that the random-access version of quick_merge_sort runs in O(n²). The culprit is the random-access nth_element, which also means that the libc++ implementation of std::nth_element is quadratic.
The text was updated successfully, but these errors were encountered:
I tried to change the implementation of nth_element for random-access iterators to miniselect's implementation of Andrei Alexandrescu's QuickselectAdaptive selection algorithm. It is very slightly slower than the libc++ algorithm on average, but correctly handles the killer input without going quadratic:
Next step is to steal the miniselect implementation and adapt it as needed.
This makes quick_merge_sort O(n log n) instead of O(n²) like it used to
be (the libc++ implementation of std::nth_element used until then was
quadratic).
The new implementation was taken from Danila Kutenin's miniselect
library.
I ran a quicksort killer like the one described in #178 with the following algorithms from the library - the ones that have a quicksort-like structure:
quick_sort
pdq_sort
quick_merge_sort
(both the bidirectional rand random-access iterators versions)Here are the results:
It is quite easy to see the difference between the O(n log n) and the O(n²) algorithms there. And it clearly shows that the random-access version of
quick_merge_sort
runs in O(n²). The culprit is the random-accessnth_element
, which also means that the libc++ implementation ofstd::nth_element
is quadratic.The text was updated successfully, but these errors were encountered: