Quicksort usually performs quite well; we want to avoid the O(n2) worst case and keep it at O(n · log(n)).
The choice of pivot is important; choosing the first element is a very bad choice if the array is almost sorted. Choosing the median of the first, middle, and last elements makes it very unlikely that we will get a bad choice.
IntroSort (``introspective sort'') changes from Quicksort to a different sort for some cases:
Quicksort is easily parallelized, and no synchronization is required: each subarray can be sorted independently.
Contents Page-10 Prev Next Page+10 Index