Quick Sort, Introsort and Counting/Radix Sort: How .NET's Array.Sort Sorts

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

You wrote the textbook quick sort, the version that picks the last element as pivot, and on 10,000 random prices it came out only 45 percent slower than Array.Sort. Not bad. How long does the same code take to sort 10,000 prices that arrive already sorted: the same, twice as long, hundreds of times longer?

Second question: a developer writes the comparison (a, b) => a - b for sorting; it is short and fits the "numeric difference" logic. Is the array [int.MaxValue, -10, int.MinValue, 5] sorted correctly with it?

Partition: the Heart of Quick Sort

Quick sort is also divide and conquer, but unlike merge sort it does the work while splitting: pick a pivot, rearrange the array so that items smaller than the pivot are on the left and larger ones on the right (partition), then sort both sides recursively. There is no merge step; when the partition is done, the pivot is already in its final place. The simplest partition is Lomuto's:

// after the call: a[lo..p-1] < pivot, a[p] == pivot, a[p+1..hi] >= pivot
public static int LomutoPartition(int[] a, int lo, int hi)
{
    int pivot = a[hi];
    int i = lo; // next slot for an item smaller than the pivot
    for (int j = lo; j < hi; j++)
    {
        if (a[j] < pivot)
        {
            (a[i], a[j]) = (a[j], a[i]);
            i++;
        }
    }
    (a[i], a[hi]) = (a[hi], a[i]); // pivot to its final place
    return i;
}

During the loop the array is split into four regions: [lo, i) smaller than the pivot, [i, j) greater than or equal to the pivot, [j, hi) not scanned yet, and the pivot at the end. Every step keeps this invariant: if the element at j is smaller, it swaps with the first "large" one at i and the small region grows by one. When the loop ends, putting the pivot at i is enough. The test checks the example in the figure exactly:

[Fact]
public void LomutoPartition_PlacesPivotAtFinalIndex()
{
    int[] prices = [42, 15, 77, 8, 30, 61, 25];

    int p = QuickSort.LomutoPartition(prices, 0, prices.Length - 1);

    Assert.Equal(2, p);
    Assert.Equal(25, prices[p]);
    Assert.All(prices[..p], x => Assert.True(x < 25));
    Assert.All(prices[(p + 1)..], x => Assert.True(x >= 25));
}

Quick Sort and Bad Input

Call the partition recursively and quick sort is ready. We added a small counter to measure the recursion depth:

public static int MaxDepth { get; private set; } // instrumentation for the article

// Lomuto partition, last item as pivot: the textbook version
public static void Lomuto(int[] items)
{
    MaxDepth = 0;
    LomutoSort(items, 0, items.Length - 1, 1);
}

private static void LomutoSort(int[] a, int lo, int hi, int depth)
{
    if (lo >= hi) return;
    MaxDepth = Math.Max(MaxDepth, depth);
    int p = LomutoPartition(a, lo, hi);
    LomutoSort(a, lo, p - 1, depth + 1);
    LomutoSort(a, p + 1, hi, depth + 1);
}

If the pivot splits the array into two equal halves, the recursion depth is log₂ n and the total work is n log n. The problem is input where the pivot is the smallest or largest element every time. In a sorted array the last element is always the largest; the partition leaves the right side empty and the left side with n − 1 elements. The depth is n and the total comparisons n²/2. The test shows it in numbers:

[Fact]
public void Lomuto_SortedInput_RecursesNTimes_HoareStaysShallow()
{
    int[] sorted = [.. Enumerable.Range(0, 5_000)];

    QuickSort.Lomuto([.. sorted]);
    int lomutoDepth = QuickSort.MaxDepth;
    QuickSort.Hoare([.. sorted]);
    int hoareDepth = QuickSort.MaxDepth;

    Assert.Equal(4_999, lomutoDepth);
    Assert.True(hoareDepth <= 13, $"hoare depth {hoareDepth}");
}

On 5,000 sorted elements the depth is 4,999. That is not just slowness: as we saw in the series' fifth post, once the depth reaches a few tens of thousands the process dies with a stack overflow. Sorted or nearly sorted input is one of the most common inputs in real life; re-sorting a list that came from the database with ORDER BY is exactly this case.

The first remedy is to pick the pivot at random. With a random pivot no fixed input is always bad; the expected depth is O(log n). Still, the chance of an unlucky run is not zero, and results are not reproducible:

// random pivot: no fixed input is always bad
public static void RandomPivot(int[] items, Random random)
{
    RandomSort(items, 0, items.Length - 1, random);
}

private static void RandomSort(int[] a, int lo, int hi, Random random)
{
    if (lo >= hi) return;
    int r = random.Next(lo, hi + 1);
    (a[r], a[hi]) = (a[hi], a[r]); // move the random pivot to the end, then Lomuto as usual
    int p = LomutoPartition(a, lo, hi);
    RandomSort(a, lo, p - 1, random);
    RandomSort(a, p + 1, hi, random);
}

Hoare Partition and Median-of-Three

The second remedy is to pick the pivot more cleverly and to partition more efficiently. Hoare's original partition uses two pointers moving inward from both ends; when it finds two elements on the wrong sides, it swaps them. On average it does three times fewer swaps than Lomuto and splits an array full of equal values evenly. Taking the median of the first, middle and last elements as the pivot (median-of-three) turns sorted and reverse-sorted input into the best case:

// Hoare partition with median-of-three pivot; recurse on the smaller side, loop on the larger
public static void Hoare(int[] items)
{
    MaxDepth = 0;
    HoareSort(items, 0, items.Length - 1, 1);
}

private static void HoareSort(int[] a, int lo, int hi, int depth)
{
    while (lo < hi)
    {
        MaxDepth = Math.Max(MaxDepth, depth);
        int p = HoarePartition(a, lo, hi);
        // smaller half by recursion, bigger half by the loop: stack depth stays O(log n)
        if (p - lo < hi - p)
        {
            HoareSort(a, lo, p, depth + 1);
            lo = p + 1;
        }
        else
        {
            HoareSort(a, p + 1, hi, depth + 1);
            hi = p;
        }
    }
}

// after the call: every item in a[lo..p] <= every item in a[p+1..hi]
public static int HoarePartition(int[] a, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;
    int pivot = MedianOfThree(a[lo], a[mid], a[hi]);
    int i = lo - 1, j = hi + 1;
    while (true)
    {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i >= j) return j;
        (a[i], a[j]) = (a[j], a[i]);
    }
}

private static int MedianOfThree(int x, int y, int z) =>
    Math.Max(Math.Min(x, y), Math.Min(Math.Max(x, y), z));

The second important idea in HoareSort is "recurse on the smaller side, loop on the larger". Every recursive call goes into a part at most half the size; however bad the pivot, the stack depth cannot exceed log₂ n. With a bad pivot the time can still climb to O(n²), but the process does not die with a stack overflow. On the 5,000 sorted elements in the test the depth stays below 13.

Hoare partition's return value differs from Lomuto's: it is not the pivot's final place but the boundary between the two sides. That is why the recursion runs on [lo, p] and [p + 1, hi], without leaving p out. Carrying Lomuto's p - 1/p + 1 bounds over here is quick sort's most classic off-by-one bug. All three versions pass the same test: empty, single-element, all-equal, sorted, reverse-sorted, many duplicates and random inputs that include int.MinValue and int.MaxValue.

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.QuickSortTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (626ms)

Test run summary: Passed!
  total: 6
  failed: 0
  succeeded: 6

.NET's Array.Sort: Introsort

In practice quick sort is usually the fastest comparison sort: it works in place, accesses memory sequentially and has a very tight inner loop. But its worst case is O(n²). Introsort (introspective sort) combines three algorithms to solve that, and .NET's Array.Sort uses exactly this. According to the Remarks section on Microsoft Learn:

• If the partition size is 16 elements or fewer, insertion sort is used.
• If the number of partitions exceeds 2 · log n (n being the length of the range being sorted), it switches to heapsort.
• In every other case quick sort is used.

The logic: quick sort normally finishes at a depth around log n. If the depth goes past twice that, the pivots are being chosen badly over and over; at that point introsort switches to heapsort, whose worst case is also O(n log n), and caps the losses. On small parts the insertion sort from the series' previous post takes over. The result is O(n log n) in every case, with constants close to quick sort's. The documentation also states explicitly that this sort is unstable. Sort on Span<T> and List<T> uses the same algorithm. We will write heapsort itself in the series' heap post.

The benchmark compares the three implementations on 10,000 random and sorted elements:

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method             | N     | Input  | Mean         | Ratio  | Allocated |
|------------------- |------ |------- |-------------:|-------:|----------:|
| ArraySort          | 10000 | random |    157.76 us |   1.01 |         - |
| LomutoLastPivot    | 10000 | random |    226.81 us |   1.45 |         - |
| HoareMedianOfThree | 10000 | random |    204.24 us |   1.30 |         - |
|                    |       |        |              |        |           |
| ArraySort          | 10000 | sorted |     33.81 us |   1.00 |         - |
| LomutoLastPivot    | 10000 | sorted | 25,332.58 us | 749.48 |         - |
| HoareMedianOfThree | 10000 | sorted |     60.09 us |   1.78 |         - |

The answer to the first opening question: the textbook quick sort, 45 percent behind on random input, is 749 times slower on sorted input, 25 ms. The Hoare version with median-of-three gets even faster on sorted input, because every pivot is the exact median. Array.Sort leads in both cases: 34 µs on sorted input. The measurements ran while other work was running on the machine; look at the ratios.

The Lower Bound of Comparison Sorting

Is there anything better than introsort? For any algorithm that sorts only by asking "is a less than b?", the answer is no. The intuition: n elements have n! different orderings, and the algorithm must find the right one. Each comparison is a two-answer question, so at best it halves the possibilities. Reducing n! possibilities to one needs at least log₂(n!) questions, and log₂(n!) is roughly n log₂ n. That is why Ω(n log n) is a lower bound for comparison sorts; merge sort, heapsort and introsort already reach it. The proof with a decision tree and the meaning of Ω notation are in the Big-O and Complexity series post "What Is Big-O Notation".

The only way past this bound is not to compare: use the structure of the keys, for example that they are integers in a small range.

Sorting Without Comparing: Counting and Radix Sort

Bookstore's online exam module holds the 0–100 grades of 1 million students. With 101 distinct keys there is no need to compare: count how many times each grade appears, then write the counts out in order. The stable version of counting sort computes where each key starts in the output with a prefix sum:

// keys in [0, maxKey]: O(n + k) time, O(n + k) memory, stable
public static T[] CountingSort<T>(T[] items, Func<T, int> key, int maxKey)
{
    int[] counts = new int[maxKey + 2];
    foreach (T item in items) counts[key(item) + 1]++;
    for (int k = 1; k < counts.Length; k++) counts[k] += counts[k - 1]; // counts[k] = first slot for key k
    T[] output = new T[items.Length];
    foreach (T item in items) output[counts[key(item)]++] = item; // left to right: stable
    return output;
}

[Fact]
public void CountingSort_Grades_IsStable()
{
    (string Name, int Grade)[] students = [("ada", 90), ("alan", 75), ("grace", 90), ("linus", 60), ("margaret", 75)];

    (string Name, int Grade)[] sorted = NonComparisonSorts.CountingSort(students, s => s.Grade, maxKey: 100);

    Assert.Equal(["linus", "alan", "margaret", "ada", "grace"], sorted.Select(s => s.Name));
}

The prefix sum from the series' previous post is back: counts is first the frequency, then each key's start index in the output. Because we place elements in input order, Ada and Grace, who got the same grade, stay in input order. The cost is O(n + k), k being the size of the key range. If k is small it is linear; if k is large (for example the whole 32-bit range, 4 billion) it is unusable.

Radix sort gets past that limit: it splits the key into parts (digits) and does a stable counting sort for each part, starting from the least significant one (LSD, least significant digit). Sorting 32-bit keys byte by byte takes four passes, and in each pass k is only 256:

// LSD radix sort on 32-bit keys, one byte per pass: 4 stable counting passes
public static void RadixSort(uint[] items)
{
    uint[] buffer = new uint[items.Length];
    uint[] source = items, target = buffer;
    for (int shift = 0; shift < 32; shift += 8)
    {
        int[] counts = new int[257];
        foreach (uint x in source) counts[((x >> shift) & 0xFF) + 1]++;
        for (int k = 1; k < 257; k++) counts[k] += counts[k - 1];
        foreach (uint x in source) target[counts[(x >> shift) & 0xFF]++] = x;
        (source, target) = (target, source);
    }
    // 4 passes: the result is back in "items"
}

Why it works rests on stability: when sorting by the second byte, numbers whose second bytes are equal keep the order they got from the first byte. After four passes the numbers are sorted by all bytes, that is, by value. The total work is 4 · (n + 256), so O(n).

The benchmark makes two comparisons on 1 million elements: Array.Sort versus counting sort for grades between 0 and 100, and Array.Sort versus radix sort for random 32-bit keys. The ratios in the table are relative to the grades' Array.Sort; compare the key rows with each other:

| Method             | N       | Mean      | Ratio | Allocated |
|------------------- |-------- |----------:|------:|----------:|
| GradesArraySort    | 1000000 | 22.400 ms |  1.00 |         - |
| GradesCountingSort | 1000000 |  2.050 ms |  0.09 | 4000109 B |
| KeysArraySort      | 1000000 | 46.200 ms |  2.06 |         - |
| KeysRadixSort      | 1000000 |  3.782 ms |  0.17 | 4004777 B |

Counting sort sorts the grades 11 times faster than Array.Sort (2.05 ms instead of 22.4 ms), radix sort sorts the 32-bit keys 12 times faster (3.78 ms instead of 46.2 ms). The price is memory: both allocate a second array of n elements, while the in-place Array.Sort allocates nothing. They are also not general: counting sort needs a small key range, radix sort needs fixed-length keys (integers, fixed-length codes). The measurement ran while other work was running on the machine.

In Production

Check your comparer on its own. Array.Sort does not always catch an invalid comparer. According to the documentation, since .NET Framework 4.5 insertion sort and heapsort do not detect an invalid comparer, and if the sort does not complete successfully the result is undefined. Our small experiment with a broken comparer that always says "greater" when either side is odd confirms it:

// broken comparer: "greater" whenever either side is odd (not transitive, not antisymmetric)
Comparison<int> broken = (a, b) => a == b ? 0 : (a % 2 != 0 || b % 2 != 0) ? 1 : a.CompareTo(b);

n=   10: no exception, sorted=False, first items: 10, 9, 8, 7, 6, 5
n= 1000: no exception, sorted=False, first items: 353, 349, 347, 345, 315, 343

No exception at either size, and neither result is sorted. The bug is silent: if you then run binary search on a list you assume is sorted, it also gives wrong answers silently, as we will see in the series' next post. Verify the comparer with a property-based test (transitivity for three random values, and Compare(a, b) == -Compare(b, a)).

If your sort key is a small integer range (a status code, a score, a day number), consider counting sort, especially if you sort a large list over and over on every request. Otherwise leave Array.Sort alone.

Common Pitfalls

a - b in a comparison. The answer to the second opening question:

a - b       : 2147483647, -2147483648, -10, 5
a.CompareTo : -2147483648, -10, 5, 2147483647

int.MaxValue - (-10) overflows and gives a negative number; according to the comparer, int.MaxValue is now less than -10. This bug, invisible while values are small, shows up at boundary values or with large IDs. Always use a.CompareTo(b) or Comparer<T>.Default.

Putting the textbook quick sort in production. The version that picks the last element as pivot is 749 times slower on sorted input and kills the process with a stack overflow on large input. If you have to write your own quick sort, at least use median-of-three and recurse on the smaller side.

Using Hoare partition with Lomuto's bounds. In Hoare, p is not the pivot's final place; recursing on [lo, p - 1] and [p + 1, hi] leaves the element at p out of both parts, and the result silently comes out wrongly sorted.

Using counting sort over a wide range. If keys are between 0 and 1 billion, counts is a 4 GB array. Do not pick counting sort without comparing k with n; for a wide range, radix sort or Array.Sort is the right choice.

A Small Experiment

★☆☆ Add RandomPivot to QuickSortBenchmarks and measure it on sorted input. How far is it from median-of-three? Does the result change when you run the same benchmark twice?

★★☆ Sort a 10,000-element array where every element is equal with Lomuto and Hoare and look at MaxDepth. Why does Lomuto collapse here too? Fix it with a three-way partition (Dijkstra's "Dutch national flag" approach: smaller, equal, larger).

★★★ Write a simple introsort: add a depth counter to Hoare quick sort, hand a part over to heapsort when the depth passes 2 · log₂ n (for now, by filling and draining a PriorityQueue), and finish parts smaller than 16 with insertion sort. How does it behave on the sorted input that kills the textbook quick sort?

The real reward of sorting is searching: in a sorted array you can find anything in log n steps. In the next post we write binary search in depth: invariants with half-open ranges, lower and upper bound, the negative return value of Array.BinarySearch, and finding the minimum shipping capacity with "binary search on the answer".