Intro

Quick sort partitions the array around a pivot so smaller elements go left and larger go right, then recursively sorts the partitions. It is often the fastest comparison sort in practice due to excellent cache behavior and low constant factors, but it has a worst-case O(n²) if pivots are consistently bad. Production implementations use randomized pivots or introsort (fallback to heapsort) to guarantee O(n log n) worst case.

Mechanism

Choose a pivot, partition the array in-place so all elements less than the pivot are to its left and all greater are to its right, then recurse on both sides. The pivot is in its final sorted position after partitioning.

graph TD
  A[quickSort A from l to r] --> B{l at least r}
  B -->|Yes| R[return]
  B -->|No| C[Choose pivot]
  C --> D[Partition A around pivot]
  D --> E[Get pivot index p after partition]
  E --> F[quickSort A from l to p minus 1]
  E --> G[quickSort A from p plus 1 to r]
  F --> R
  G --> R

Complexity

Properties: in-place (Lomuto/Hoare partition), not stable, excellent cache locality.

C# Implementation (Lomuto partition, randomized pivot)

private static readonly Random _rng = new();

public static void QuickSort(int[] a, int left, int right)
{
    if (left >= right) return;

    // Randomized pivot to avoid O(n²) on sorted/reverse-sorted input
    int pivotIdx = _rng.Next(left, right + 1);
    (a[pivotIdx], a[right]) = (a[right], a[pivotIdx]);

    int p = Partition(a, left, right);
    QuickSort(a, left, p - 1);
    QuickSort(a, p + 1, right);
}

private static int Partition(int[] a, int left, int right)
{
    int pivot = a[right];
    int i = left - 1;
    for (int j = left; j < right; j++)
    {
        if (a[j] <= pivot)
        {
            i++;
            (a[i], a[j]) = (a[j], a[i]);
        }
    }
    (a[i + 1], a[right]) = (a[right], a[i + 1]);
    return i + 1;
}

When to Use

• General-purpose in-memory sorting: quick sort's cache-friendly access pattern makes it faster than merge sort in practice for most inputs.
• When stability is not required: quick sort is not stable; use merge sort if equal elements must preserve their original order.
• With randomized pivot or introsort: .NET's Array.Sort uses introsort (quick sort + heap sort fallback) to guarantee O(n log n) worst case.

Avoid naive quick sort (fixed pivot) on inputs that may be sorted or reverse-sorted — it degrades to O(n²).

Pitfalls

Fixed Pivot on Sorted Input

What goes wrong: using the first or last element as the pivot on already-sorted or reverse-sorted input causes every partition to be maximally unbalanced (one side has n-1 elements, the other has 0). This degrades to O(n²) time and O(n) stack depth, causing a stack overflow for large n.

Mitigation: use a randomized pivot (pick a random index and swap it to the end before partitioning) or median-of-three (pick the median of first, middle, last elements). .NET's Array.Sort uses introsort, which switches to heapsort when recursion depth exceeds 2×log(n).

Not Handling Duplicate Keys

What goes wrong: standard Lomuto/Hoare partition degrades to O(n²) on arrays with many duplicate keys (e.g., sorting 10,000 elements where 90% are the same value). All duplicates end up on one side of every partition.

Mitigation: use three-way partitioning (Dutch National Flag algorithm) for inputs with many duplicates. It partitions into three regions: less than, equal to, and greater than the pivot, so all equal elements are placed in their final positions in one pass.

Tradeoffs

Decision rule: use Array.Sort (introsort) for general-purpose in-memory sorting. Implement quick sort directly only when you need fine-grained control (e.g., three-way partition for duplicate-heavy data). Use merge sort when stability is required.

Questions

References

• Quicksort (Wikipedia) — Lomuto and Hoare partition schemes, randomization, and introsort.

• Quick sort (cp-algorithms) — practical implementation tips including three-way partition for duplicate keys.

• Introsort (Wikipedia) — the hybrid algorithm used by .NET's Array.Sort; combines quick sort, heapsort, and insertion sort to guarantee O(n log n) worst case while keeping quick sort's cache efficiency.

• Sorting algorithms comparison (Big-O Cheat Sheet) — quick reference for time and space complexity of all common sorting algorithms.