Quicksort usually performs quite well; we want to avoid the O(n²) 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:

• Change to Insertion Sort when the size becomes small ( &le 20), where Insertion Sort may be more efficient.

• Change to Heapsort after a certain depth of recursion, which can protect against the unusual O(n²) worst case.

Quicksort is easily parallelized, and no synchronization is required: each subarray can be sorted independently.

Contents    Page-10    Prev    Next    Page+10    Index