Quick sort

Quick sort is also divide and conquer, but it does the hard work before recursing instead of after. Pick one value, the pivot, and rearrange the array so every smaller value is on its left and every larger value is on its right. The pivot is now in its final position. Then sort the left part and the right part the same way. No merge step is needed.

Partitioning (Lomuto scheme)

Put the pivot at the end. Walk through the other values with j, and keep a boundary i: everything before i is smaller than the pivot. When a[j] is smaller, swap it to position i and move the boundary. Finally swap the pivot to position i.

1static void QuickSort(int[] a, int lo, int hi)2{3    if (lo >= hi) return;4    int p = Partition(a, lo, hi);    // pivot ends at index p, in its final place5    QuickSort(a, lo, p - 1);         // smaller values6    QuickSort(a, p + 1, hi);         // bigger values7}8 9static int Partition(int[] a, int lo, int hi)10{11    int mid = lo + (hi - lo) / 2;12    (a[mid], a[hi]) = (a[hi], a[mid]);   // use the middle value as pivot, moved to the end13    int pivot = a[hi];14 15    int i = lo;                          // a[lo..i-1] < pivot16    for (int j = lo; j < hi; j++)17    {18        if (a[j] < pivot)19        {20            (a[i], a[j]) = (a[j], a[i]);21            i++;22        }23    }24    (a[i], a[hi]) = (a[hi], a[i]);       // pivot into its final place25    return i;26}27 28int[] data = { 7, 2, 9, 4, 10, 1, 6, 3, 8, 5 };29QuickSort(data, 0, data.Length - 1);   // sort the whole array30Console.WriteLine(string.Join(" ", data));

1 2 3 4 5 6 7 8 9 10

Good pivots, bad pivots

If the pivot splits the array roughly in half every time, there are about log n levels, each doing O(n) work: O(n log n). If the pivot is always the smallest or largest value, each partition removes only one item. Then there are n levels: O(n²), and the recursion can be deep enough to overflow the stack. Taking the last item as pivot on already sorted data does exactly that; try it in the widget above.

Quick sort in .NET: introsort

Array.Sort, List<T>.Sort and Span<T>.Sort use introsort (introspective sort): quick sort with a median-of-three pivot, plus two safety nets. Pieces of 16 or fewer items are finished with insertion sort. If the recursion gets suspiciously deep (a bad-pivot input), it switches to heap sort, which is always O(n log n). You get quick sort’s speed with a guaranteed worst case.

Bonus: quickselect

To find the k-th smallest value you do not need to sort everything. After one partition you know the pivot’s exact rank. If it is the one you want, stop; otherwise continue in one side only. On average that is n + n/2 + n/4 + … ≈ 2n steps: O(n).

1// k = 1 means the smallest value2static int KthSmallest(int[] a, int k)3{4    int lo = 0, hi = a.Length - 1, target = k - 1;5    while (true)6    {7        int p = Partition(a, lo, hi);   // the same Partition as above8        if (p == target) return a[p];9        if (p < target) lo = p + 1;     // the answer is on the right10        else hi = p - 1;                // the answer is on the left11    }12}13 14Console.WriteLine(KthSmallest([7, 2, 9, 4, 10, 1, 6, 3, 8, 5], 3));

3

1static void SortColors(int[] a)2{3    int low = 0, mid = 0, high = a.Length - 1;4    while (mid <= high)5    {6        if (a[mid] == 0)7        {8            (a[low], a[mid]) = (a[mid], a[low]);9            low++; mid++;10        }11        else if (a[mid] == 1)12        {13            mid++;14        }15        else16        {17            (a[mid], a[high]) = (a[high], a[mid]);18            high--;            // the swapped-in value is unchecked: keep mid19        }20    }21}22 23int[] a = { 2, 0, 2, 1, 1, 0 };24SortColors(a);25Console.WriteLine(string.Join(" ", a));

0 0 1 1 2 2