Daniel Hulme <pho### [at] isticorg> wrote:
> I have no idea why after all these years people still think quicksort is
> a good idea. It's so trivial to find an example where it takes O(n^2)
> time.

  It's certainly not very trivial to find such an example of the choice
of pivot in the paritioning is smart. Simply making a median-of-3 pivot
choice makes finding such an example non-trivial. Moreover, if the
middle item of the median choice is taken with some randomization to it,
good luck finding a patological example.

  Moreover, quicksort is handy because it can easily be enhanced to
sort small partitions with insertion sort, making it noticeably faster.
(Heapsort, for instance, cannot be enhanced like this. Mergesort can be,
but the problem with mergesort is its additional memory requirements,
at least when sorting arrays.)

  Oh, but of course there's the array where every value is the same.
It's rather trivial to stop partitioning when no swaps were made.

  Sure, it's still possible for a pathological case to happen, but
finding one is not trivial.

-- 
                                                          - Warp

Post a reply to this message