1.1 Choosing a better pivot

The worst-case behavior of quicksort is not merely a theoretical problem. When quicksort is used in web services, for example, it is possible for an attacker to deliberately exploit the worst case performance and choose data which will cause a slow running time or maximize the chance of running out of stack space. See competitive analysisCompetitive analysis shows how on-line algorithms perform and demonstrates the power of randomization in algorithms. For many algorithms, the performance is not dependent on the values of the data, only the amount. An example of one that is data dependent for more discussion of this issue.

Sorted or partially sorted data is quite common in practice and the naïve implementation which selects the first element as the pivot does poorly with such data. To avoid this problem the middle element can be used. This works well in practice but attacks can cause worst-case performance.

A better optimization can be to select the median element of the first, middle and last elements as the pivot. Adding two randomly selected elements resists chosen data attacks, more so if a cryptographically sound random number generator is used to reduce the chance of an attacker predicting the "random" elements. The use of the fixed elements reduces the chance of bad luck causing a poor pivot selection for partially sorted data when not under attack. These steps increase overhead, so it may be worth skipping them once the partitions grow small and the penalty for poor pivot selection drops.

Finding the true median value and using it as the pivot can be done if the number of elements is large enough to make it necessary but this is seldom done in practice.

1.2 Partitioning concerns

As virtually all of the quicksort computation time is spent partitioning, a good partitioning implementation is important. In particular, if all of the elements being partitioned are equal, the above partition algorithm degenerates into the worst case, needlessly swapping identical elements and returning the worst possible pivot. This becomes a serious problem in any datasets which contain many equal elements, as many of the 'bottom tier' of partitions will become uniform.

A good variation in such cases is to test separately for equal elements and store these in a 'fat pivot' in the center of the partition. An implementation of this variation implemented in C is shown below. Another, easier alternative is to avoid recursing if the left-most and right-most elements are equal after partitioning.

1.3 Other optimizations

Another optimization is to switch to a different sorting algorithm once the list becomes small, perhaps ten or less elements. Selection sort might be inefficient for large data sets, but it is often faster than Quicksort on small lists.

One widely used implementation of quicksort, that in the 1997 Microsoft C library, used a cutoff of 8 elements before switching to insertion sortInsertion sort is a simple sort algorithm in which the sorted array (or list) is built one entry at a time. It is much less efficient than the more advanced algorithms such as Quicksort, Heapsort, or Merge sort, but its advantages are: Simple to implement, asserting that testing had shown that to be a good choice. It used the middle element for the partition value, asserting that testing had shown that the median of three algorithm did not, in general, increase performance.

Sedgewick (1978) suggested an enhancement to the use of simple sorts for small numbers of elements, which reduced the number of instructions required by postponing the simple sorts until the quicksort had finished, then running an insertion sort over the whole array. This is effective because insertion sort requires only O(kn) time to sort an array where every element is less than k places from its final position.

LaMarca and Ladner (1997) consider "The Influence of Caches on the Performance of Sorting", a very significant issue in microprocessor systems with multi-level caches and high cache miss times. They conclude that while the Sedgewick optimization decreases the number of instructions, it also decreases locality of cache references and worsens performance compared to doing the simple sort when the need for it is first encountered. However, the effect was not dramatic and they suggested that it was starting to become more significant with more than 4 million 64 bit float elements. Greater improvement was shown for other sorting types.

Because recursion requires additional memory, Quicksort has been implemented in a non-recursive, iterative form. This has the advantage of predictable memory use regardless of input, and the disadvantage of considerably greater code complexity. Those considering iterative implementations of quicksort would do well to also consider introsortIntrosort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort, switching to heapsort once the recursion depth exceeds a preset value. The resulting sort combines the best of both, with a worst-case O n l or heapsort instead.

A simple alternative for reducing Quicksort's memory consumption uses true recursion only on the smaller of the two sublists and tail recursion on the larger. This limits the additional storage of Quicksort to O(log n). The procedure quicksort in the preceding pseudocode would be rewritten as

function quicksort(a, left, right) while right > left select a pivot value a[pivotIndex] pivotNewIndex := partition(a, left, right, pivotIndex) if (pivotNewIndex-1) - left < right - (pivotNewIndex+1) quicksort(a, left, pivotNewIndex-1) left := pivotNewIndex+1 else quicksort(a, pivotNewIndex+1, right) right := pivotNewIndex-1

2 Introsort optimization

Main article: Introsort

An optimization of quicksort which is becoming widely used is introspective sort, often called introsort. This starts with quicksort and switches to heapsort when the recursion depth exceeds a preset value. This overcomes the overhead of increasingly complex pivot selection techniques while ensuring O(n log n) worst-case performance. Musser reported that on a median-of-3 killer sequence of 100,000 elements running time was 1/200th that of median-of-3 quicksort. Musser also considered the effect of Sedgewick's delayed small sorting on caches, reporting that it could double the number of cache misses when used on arrays, but its performance with double-ended queues was significantly better. See introsort for more details.

3 Competitive sorting algorithms

The most direct competitor of Quicksort is heapsort. Heapsort is typically somewhat slower than Quicksort, but the worst-case running time is always O(n log n). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. If it's known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it. Heapsort also has the important advantage of using only constant additional space (heapsort is in-place), whereas even the best variant of Quicksort uses O(log n) space. However, heapsort requires efficient random access to be practical.

Quicksort is a space-optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, Quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order.

4 Relationship to selection

A simple selection algorithm, which chooses the kth smallest of a list of elements, works nearly the same as quicksort, except instead of recursing on both sublists, it only recurses on the sublist which contains the desired element. This small change lowers the average complexity to linear or O(n) time. A variation on this algorithm brings the worst-case time down to O(n) (see selection algorithm for more information).

Conversely, once we know a worst-case O(n) selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of Quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.

5 Sample implementations

Main article: Quicksort implementations

Here we demonstrate a number of quicksort implementations in various languages. We show only some of the most popular or unique ones here; for additional implementations, see the article quicksort implementations.

5.1 C

void sort(int array[], int begin, int end) { if (end > begin) { int pivot = array[begin]; int l = begin + 1; int r = end; while(l < r) { if (array[l] <= pivot) { l++; } else { r--; swap(array[l], array[r]); } } l--; swap(array[begin], array[l]); sort(array, begin, l); sort(array, r, end); } }

5.2 C++

#include #include #include template void sort(T begin, T end) { if (begin != end) { T middle = partition (begin, end, bind2nd( less::value_type>(), *begin)); sort (begin, middle); sort (max(begin + 1, middle), end); } }

5.3 Java

This example also demonstrates a generic quicksort, rather than just one on a set of integers.

import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private void swap(Object[] array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private int partition(Object[] array, int begin, int end, Comparator cmp) { int index = begin + RND.nextInt(end - begin + 1); Object pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private void qsort(Object[] array, int begin, int end, Comparator cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public void sort(Object[] array, Comparator cmp) { qsort(array, 0, array.length - 1, cmp); } }

5.4 Python

def partition(array, begin, end, cmp): while begin < end: while begin < end: if cmp(array[begin], array[end]): (array[begin], array[end]) = (array[end], array[begin]) break end -= 1 while begin < end: if cmp(array[begin], array[end]): (array[begin], array[end]) = (array[end], array[begin]) break begin += 1 return begin def sort(array, cmp=lambda x, y: x > y, begin=None, end=None): if begin is None: begin = 0 if end is None: end = len(array) if begin < end: i = partition(array, begin, end-1, cmp) sort(array, cmp, begin, i) sort(array, cmp, i+1, end)

5.5 Joy

DEFINE sort == [small][] [uncons [>] split] swap] dip cons concat] binrec .

1 =

swap] dip cons concat] binrec .

1.1 Haskell

sort :: (Ord a) => [a] -> [a] sort [] = [] sort (pivot:rest) = sort [y | y <- rest, y < pivot] ++ [pivot] ++ sort [y | y <- rest, y >=pivot]

1.2 Prolog

append([], L, L). append([H | L1], L2, [H | Result]) :- append(L1, L2, Result). partition([], _, [], []). partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right). partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right). qsort([],[]). qsort([H | Tail], Sorted) :- partition(Tail, H, Left, Right), qsort(Left, SortedLeft), qsort(Right, SortedRight), append(SortedLeft, [X | SortedRight], Sorted).

1.1 External links

• animated Quicksort

1.2 References

• Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961
• R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847857, 1978.
• David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
• A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370-379.

Sort algorithms

<Hide>