Quick sort works very well on large sets of data. It applies divide and conquer as follows.

1. Divide: divide the array A[0], A[1] … A[n−1] into two subarrays around a pivot element A[k].
2. Conquer: sort the left part A[0] … A[k−1] and the right part A[k+1] … A[n−1] recursively.
3. Combine: since the two subarrays are already sorted in the previous step, there is no need to combine.

Left part: all elements ≤ A[k] (the pivot element). Right part: all elements ≥ A[k].

Application: Google uses an advanced form of quick sort to sort the web pages it finds as a result.

Algorithm QuickSort(p, q)

Algorithm QuickSort(p, q)
/* Sorts the elements a[p], ..., a[q] which reside in the global
   array a[1:n] into ascending order; a[n+1] is considered to be
   defined and must be ≥ all the elements in a[1:n]. */
{
    if (p < q) then            // If more than one element
    {
        // divide P into two subproblems
        k := Partition(a, p, q + 1);   // k is the position of the partitioning element
        // solve the subproblems
        QuickSort(p, k - 1);
        QuickSort(k + 1, q);
    }
}

Algorithm Partition(a, low, high)

Algorithm Partition(a, low, high)
// Purpose: divide the array into parts such that elements to the left
//          of the pivot are ≤ pivot and elements to the right of the key are ≥ pivot.
// low  : the position of the first element of array a
// high : the position of the last element (plus the sentinel)

pivot ← a[low]
i ← low
j ← high
while (i ≤ j)
    do i ← i + 1  while (pivot ≥ a[i])
    do j ← j - 1  while (pivot < a[j])
    if (i < j) exchange(a[i], a[j])
end while
exchange(a[j], a[low])
return j

Example: trace for n = 8

Explain the partition exchange sort algorithm and trace it for n = 8 elements: 24, 12, 35, 23, 45, 34, 20, 48.

The initial call is QuickSort(1, 8), which calls k := Partition(a, 1, 9). This returns k = 4, so the next calls are QuickSort(1, 3) and QuickSort(5, 8).

Partition(a, 1, 9): low = 1, high = 9, pivot = 24, i = 1, j = 9

Finally exchange a[j] = a[4] with a[low] = a[1]:

Return j = 4. The pivot 24 is now in its final position.

Analysis of quick sort

1. Best case

The key element is present exactly at the centre, dividing the array into two equal parts. The recurrence relation is:

T(n) = 0                       if n = 1
     = T(n/2) + T(n/2) + n     otherwise

Here the two T(n/2) terms are the time to sort the left and right parts, and n is the partition time.

(a) Substitution method

T(n) = T(n/2) + T(n/2) + n
     = 2T(n/2) + n
     = 2[2T(n/2²) + n/2] + n
     = 2²T(n/2²) + 2n
     = 2³T(n/2³) + 3n
       ⋮
     = 2ⁱT(n/2ⁱ) + i·n

Let n = 2ⁱ, so i = log₂n:
     = n·T(1) + n·log₂n
     = n·0 + n·log n

⇒ T(n) = Θ(n log n)       (best case)

(b) Master's theorem

T(n) = 2T(n/2) + n, so a = 2, b = 2 and f(n) = n¹·logᵖn with k = 1 and p = 0. Since log_b^a = log₂² = 1 = k and p = 0 > −1, the result is Θ(nᵏ log^p+1 n) = Θ(n log n).

2. Worst case

The worst case occurs when, at each invocation of the procedure, the current array is partitioned into two subarrays with one of them empty. This happens if all the elements are already arranged in ascending or descending order.

For example, [22, 33, 44, 55] yields the following sequence of partitions:

22 [33, 44, 55]
22  33 [44, 55]
22  33  44 [55]

T(n) = 0                       if n = 1
     = T(0) + T(n-1) + n       otherwise

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
       ⋮
     = T(n-n) + 1 + 2 + … + (n-1) + n
     = 0 + 1 + 2 + … + n
     = n(n+1)/2  ≤  n²   for n ≥ 0      (f(n) ≤ c·g(n))

⇒ T(n) = O(n²)

3. Average case

The array may not be partitioned into two equal subarrays, but it also may not be as skewed as in the worst case.

Here (n+1) is the partition.
Multiply by n on both sides:

Put n = n−1:

Note that T(0) = T(1) = 0.

perform 2 & 3

Divide by n(n+1):

Substituting repeatedly:

Stable sorting algorithm

A sorting method is said to be stable if, at the end of the method, identical elements occur in the same order as in the original list.

Quick sort is not a stable sorting method, but merge sort is a stable sorting method.

Randomized quick sort algorithm

QuickSort() in the previous section takes O(n log n) average time and O(n²) worst-case time, where n² > n log n. So QuickSort() is improvised to RQuickSort(), which works on any input and runs in O(n log n) in all cases.

While sorting the array a[p:q], instead of picking a[p], pick a random element among a[p], …, a[q] as the partition element.

Algorithm RQuickSort(p, q)
/* Sorts the elements a[p], ..., a[q] which reside in the global
   array a[1:n] into ascending order. a[n+1] is considered to be
   defined and must be ≥ all the elements in a[1:n]. */
{
    if (p < q) then
    {
        if ((q - p) > 5) then
            Interchange(a, Random() mod (q - p + 1) + p, p);
        j := Partition(a, p, q + 1);    // j is the position of the partitioning element
        RQuickSort(p, j - 1);
        RQuickSort(j + 1, q);
    }
}

Why it is a Las Vegas algorithm

1. It uses randomness to sort the elements, and
2. it always gives the correct answer,
3. or it informs about the failure.

The randomizer is invoked only if (q − p) > 5, because if there are fewer elements, the randomizer alone takes more time than the rest of the computation.

Average time

Let A(n) be the average time of RQuickSort on any input of n elements.

This holds because the number of elements in the second part will be 0, 1, 2, …, n−2 or n−1, all with an equal probability of 1/n. This A(n) equation is the same as the average-case equation of quick sort, so A(n) = O(n log n).

Randomized algorithm for sorting

Algorithm RSort(a, n)
// Sort the elements a[1:n]
{
    Randomly sample s elements from a[ ];
    Sort this sample;
    Partition the input using the sorted sample as partition keys;
    Sort each part separately;
}