Quicksort Sorting

Quicksort sorting is an O(N²) algorithm for sorting a list of N items using comparisons that on average runs in O(N lgN) time. The idea is to reorganize the input sequence into two adjacent subsequences (partitions) such that all the elements in the first partition are less than all those in the second. As a result, no further movement of items between the two sections is necessary and the two sections can themselves be sorted (recursively) independently. We can continue this process, dividing the array into smaller and smaller partitions that are all correctly ordered with respect to each other.

When the partition size is reduced to one the entire sequence will be sorted. However, the maximum partition size also limits the number of inversions in the sequence, which in turn limits the execution time of insertion sorting (see the Insertion Sorting page). The number of inversions in a sequence partitioned by quicksort is equal to the sum of the numbers of inversions in the individual partitions (why?). Therefore, once the maximum partition size is reduced to some constant, the total number of inversions is linear in the size of the entire sequence. Since insertion sorting has better constant factors than quicksort, a common modification to the quicksort algorithm is to apply insertion sorting once the maximum partition size is reduced below some predetermined threshold size.

To partition a sequence, quicksort chooses a pivot element from the sequence and then swaps elements in the array to place elements less than the pivot in the first partition and those greater in the other. Each partitioning operation requires linear time in the size of the subsequence being partitioned. In the extreme case, the maximum partitition size is reduced by one on each step, leading to O(N²) running time. The best case is to find pivots that divide the subsequence into equal-sized partitions. There are various strategies for choosing such pivots, including taking small random samples of the subsequence.

The variant presented here chooses as the pivot the median of the first, last, and middle elements of a subsequence. It switches to ordinary insertion sorting when the maximum partition size is reduced to a certain size, initially 4.

The partitioning steps use an algorithm due to Nico Lomuto: the selected pivot is swapped to the beginning of the subsequence to be partitioned, and the rest of the array is swept, swapping elements less than the pivot to the left end of the array (after the pivot). As a final step, the pivot element is swapped once more to the dividing line between the partitions, which is its correct position in the sequence (why?). Since it therefore need not participate in further partitioning, any further partitioning operations operate on strictly smaller subsequences (avoiding infinite recursion). Each subsequence being partitioned is shown slightly separated from the rest of the array, with elements known to be less than the pivot colored purple and those known to be greater than or equal colored green.