3 ms·

Quicksort is broken. Is it worth fixing?

24 points by dryman 15y ago

fatjokes 15y ago
the bigger news here is that people are still using angelfire. i half expected that the ads on top were from linkexchange.
shin_lao 15y ago
It's curious the OP doesn't mention introsort (http://en.wikipedia.org/wiki/Introsort http://en.wikipedia.org/wiki/Introsort). AFAIK most standard libraries use introsort instead of quicksort. Introsort uses heapsort when the recursion is too deep and insertsort when the entry is too small.
- ableal 15y ago
  The article seems pretty old - at least from 2004 ( http://wayback.archive.org/web/*/http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm http://wayback.archive.org/web/*/http://www.angelfire.com/pq... ), probably even older. Angelfire was popular in the late 1990s ...
ssdsa 15y ago
A really nice essay about Quicksort and it's quirks and border cases. Worth a read! On the other hand, when developing an application, you should think twice if you really need to write your own sorting routine. Better stick with the system library unless you have some use case that really requires your own sorting implementation.
srean 15y ago
http://stackoverflow.com/questions/2105737/has-anyone-seen-this-improvement-to-quicksort-before http://stackoverflow.com/questions/2105737/has-anyone-seen-t... Another nice discussion on how to deal with the duplicate problem.
primecommenter 15y ago
It is possible to find the median in linear time (quickselect). Pivoting on the median makes quicksort optimal (O(n log(n))) while only using constant space. This is rarely used in practice because the overhead is large compared to the probability of being given a worst-case problem.
fridek 15y ago
There is an algorithm for calculating median in O(n). I was wondering if choosing a pivot that is always a median would speed up quicksort. In theory it should always give O(n log n) time, as recursive calls would always take a half of input array.
lucian1900 15y ago
Variations of mergesort are starting to have overall higher throughput, while having better worst case complexity. Timsort is a good example, used in Python and JDK 7.

24 points by dryman 15y ago

the bigger news here is that people are still using angelfire. i half expected that the ads on top were from linkexchange.

shin_lao 15y ago

It's curious the OP doesn't mention introsort (http://en.wikipedia.org/wiki/Introsort http://en.wikipedia.org/wiki/Introsort). AFAIK most standard libraries use introsort instead of quicksort. Introsort uses heapsort when the recursion is too deep and insertsort when the entry is too small.

ableal 15y ago
The article seems pretty old - at least from 2004 ( http://wayback.archive.org/web/*/http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm http://wayback.archive.org/web/*/http://www.angelfire.com/pq... ), probably even older. Angelfire was popular in the late 1990s ...

ssdsa 15y ago

A really nice essay about Quicksort and it's quirks and border cases. Worth a read! On the other hand, when developing an application, you should think twice if you really need to write your own sorting routine. Better stick with the system library unless you have some use case that really requires your own sorting implementation.

srean 15y ago

http://stackoverflow.com/questions/2105737/has-anyone-seen-this-improvement-to-quicksort-before http://stackoverflow.com/questions/2105737/has-anyone-seen-t... Another nice discussion on how to deal with the duplicate problem.

primecommenter 15y ago

It is possible to find the median in linear time (quickselect). Pivoting on the median makes quicksort optimal (O(n log(n))) while only using constant space. This is rarely used in practice because the overhead is large compared to the probability of being given a worst-case problem.

fridek 15y ago

There is an algorithm for calculating median in O(n). I was wondering if choosing a pivot that is always a median would speed up quicksort. In theory it should always give O(n log n) time, as recursive calls would always take a half of input array.

lucian1900 15y ago

Variations of mergesort are starting to have overall higher throughput, while having better worst case complexity. Timsort is a good example, used in Python and JDK 7.