ZetCode

C# Introsort

last modified November 15, 2026

In this article we implement the introsort algorithm in C#. Introsort is the algorithm behind Array.Sort, List.Sort and Span.Sort. We build it from quicksort, heap sort and insertion sort, count what each part does, and compare our version with the built-in sort.

Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.

Introsort algorithm

Introsort (introspective sort) was published by David Musser in 1997. It is a quicksort that watches its own recursion depth. Quicksort is fast on average, but a sequence of bad pivots makes it O(n2). Introsort combines three algorithms:

PropertyValue
Average and worst caseO(n log n)
Best caseO(n log n)
Extra memoryO(log n) for recursion
Stableno

The heap sort fallback guarantees the O(n log n) worst case. Insertion sort is faster than quicksort on small arrays, because it has no recursion and works on neighboring elements.

C# introsort example

The following implementation follows the structure of the .NET ArraySortHelper class. It sorts an array of integers in ascending order.

Program.cs
int[] nums = [38, 27, 43, 3, 9, 82, 10, 61, 5, 77, 19, 50, 2, 94, 33, 71, 14, 66, 8, 45, 29, 12];

IntroSort(nums);
Console.WriteLine(string.Join(" ", nums));

var rnd = new Random(1);
int[] big = [.. Enumerable.Range(0, 100_000).Select(_ => rnd.Next(1000))];
IntroSort(big);
Console.WriteLine($"100,000 numbers sorted: {big.SequenceEqual(big.Order())}");

static void IntroSort(int[] arr)
{
    if (arr.Length < 2) return;

    int depthLimit = 2 * (int.Log2(arr.Length) + 1);
    Sort(arr, 0, arr.Length - 1, depthLimit);
}

static void Sort(int[] arr, int lo, int hi, int depthLimit)
{
    while (hi > lo)
    {
        int size = hi - lo + 1;

        if (size <= 16)
        {
            InsertionSort(arr, lo, hi);
            return;
        }

        if (depthLimit == 0)
        {
            HeapSort(arr, lo, hi);
            return;
        }

        depthLimit--;

        int p = Partition(arr, lo, hi);
        Sort(arr, p + 1, hi, depthLimit);
        hi = p - 1;
    }
}

static int Partition(int[] arr, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;

    if (arr[mid] < arr[lo]) Swap(arr, lo, mid);
    if (arr[hi] < arr[lo]) Swap(arr, lo, hi);
    if (arr[hi] < arr[mid]) Swap(arr, mid, hi);

    int pivot = arr[mid];
    Swap(arr, mid, hi - 1);

    int left = lo, right = hi - 1;

    while (left < right)
    {
        while (arr[++left] < pivot) { }
        while (pivot < arr[--right]) { }

        if (left >= right) break;

        Swap(arr, left, right);
    }

    if (left != hi - 1) Swap(arr, left, hi - 1);

    return left;
}

static void InsertionSort(int[] arr, int lo, int hi)
{
    for (int i = lo + 1; i <= hi; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= lo && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

static void HeapSort(int[] arr, int lo, int hi)
{
    int n = hi - lo + 1;

    for (int i = n / 2 - 1; i >= 0; i--) SiftDown(arr, lo, i, n);

    for (int end = n - 1; end > 0; end--)
    {
        Swap(arr, lo, lo + end);
        SiftDown(arr, lo, 0, end);
    }
}

static void SiftDown(int[] arr, int lo, int i, int n)
{
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = left + 1;

        if (left < n && arr[lo + left] > arr[lo + largest]) largest = left;
        if (right < n && arr[lo + right] > arr[lo + largest]) largest = right;

        if (largest == i) return;

        Swap(arr, lo + i, lo + largest);
        i = largest;
    }
}

static void Swap(int[] arr, int i, int j) => (arr[i], arr[j]) = (arr[j], arr[i]);

We sort 22 numbers and then 100,000 random numbers, which we compare with the result of LINQ's Order.

int depthLimit = 2 * (int.Log2(arr.Length) + 1);

The depth limit is the same as in .NET: two times the binary logarithm of the length, plus two. For 100,000 elements it is 34.

if (size <= 16)
{
    InsertionSort(arr, lo, hi);
    return;
}

if (depthLimit == 0)
{
    HeapSort(arr, lo, hi);
    return;
}

Before partitioning, the method checks for the two special cases. Small partitions are finished with insertion sort, partitions at the depth limit with heap sort.

int p = Partition(arr, lo, hi);
Sort(arr, p + 1, hi, depthLimit);
hi = p - 1;

The right part is sorted recursively, and the loop continues with the left part. This saves half of the recursive calls.

if (arr[mid] < arr[lo]) Swap(arr, lo, mid);
if (arr[hi] < arr[lo]) Swap(arr, lo, hi);
if (arr[hi] < arr[mid]) Swap(arr, mid, hi);

The first, middle and last elements are sorted. The middle one, the median of the three, becomes the pivot. On sorted or reversed data, the median of three is the true median, so these common inputs split evenly.

int pivot = arr[mid];
Swap(arr, mid, hi - 1);

The pivot is moved next to the end. Now arr[lo] is not greater than the pivot and arr[hi - 1] equals it. These two elements are sentinels that stop the scanning loops, so the loops need no bounds checks.

while (arr[++left] < pivot) { }
while (pivot < arr[--right]) { }

This is Hoare's partition scheme: two indexes move towards each other and swap pairs of misplaced elements. Both loops stop on elements equal to the pivot, so arrays with many duplicates are split evenly too.

if (left != hi - 1) Swap(arr, left, hi - 1);

return left;

Finally, the pivot is moved to its final position, which is returned.

$ dotnet run
2 3 5 8 9 10 12 14 19 27 29 33 38 43 45 50 61 66 71 77 82 94
100,000 numbers sorted: True

What introsort does

The next example counts the partitioning steps, the insertion sorts, the heap sort fallbacks and the maximum recursion depth for different inputs of one million elements.

Program.cs
const int N = 1_000_000;
var rnd = new Random(7);

Run("random", [.. Enumerable.Range(0, N).Select(_ => rnd.Next())]);
Run("sorted", [.. Enumerable.Range(0, N)]);
Run("reversed", [.. Enumerable.Range(0, N).Reverse()]);
Run("all equal", new int[N]);
Run("10 distinct values", [.. Enumerable.Range(0, N).Select(_ => rnd.Next(10))]);

static void Run(string name, int[] arr)
{
    Stats.Reset();
    IntroSort(arr);
    Console.WriteLine($"{name,-18} partitions {Stats.Partitions,7:N0}  insertion sorts {Stats.InsertionSorts,7:N0}  heap sorts {Stats.HeapSorts}  max depth {Stats.MaxDepth}");
}

static void IntroSort(int[] arr)
{
    if (arr.Length < 2) return;

    int depthLimit = 2 * (int.Log2(arr.Length) + 1);
    Sort(arr, 0, arr.Length - 1, depthLimit, 1);
}

static void Sort(int[] arr, int lo, int hi, int depthLimit, int depth)
{
    Stats.MaxDepth = Math.Max(Stats.MaxDepth, depth);

    while (hi > lo)
    {
        int size = hi - lo + 1;

        if (size <= 16)
        {
            Stats.InsertionSorts++;
            InsertionSort(arr, lo, hi);
            return;
        }

        if (depthLimit == 0)
        {
            Stats.HeapSorts++;
            HeapSort(arr, lo, hi);
            return;
        }

        depthLimit--;

        Stats.Partitions++;
        int p = Partition(arr, lo, hi);
        Sort(arr, p + 1, hi, depthLimit, depth + 1);
        hi = p - 1;
    }
}

static int Partition(int[] arr, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;

    if (arr[mid] < arr[lo]) Swap(arr, lo, mid);
    if (arr[hi] < arr[lo]) Swap(arr, lo, hi);
    if (arr[hi] < arr[mid]) Swap(arr, mid, hi);

    int pivot = arr[mid];
    Swap(arr, mid, hi - 1);

    int left = lo, right = hi - 1;

    while (left < right)
    {
        while (arr[++left] < pivot) { }
        while (pivot < arr[--right]) { }

        if (left >= right) break;

        Swap(arr, left, right);
    }

    if (left != hi - 1) Swap(arr, left, hi - 1);

    return left;
}

static void InsertionSort(int[] arr, int lo, int hi)
{
    for (int i = lo + 1; i <= hi; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= lo && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

static void HeapSort(int[] arr, int lo, int hi)
{
    int n = hi - lo + 1;

    for (int i = n / 2 - 1; i >= 0; i--) SiftDown(arr, lo, i, n);

    for (int end = n - 1; end > 0; end--)
    {
        Swap(arr, lo, lo + end);
        SiftDown(arr, lo, 0, end);
    }
}

static void SiftDown(int[] arr, int lo, int i, int n)
{
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = left + 1;

        if (left < n && arr[lo + left] > arr[lo + largest]) largest = left;
        if (right < n && arr[lo + right] > arr[lo + largest]) largest = right;

        if (largest == i) return;

        Swap(arr, lo + i, lo + largest);
        i = largest;
    }
}

static void Swap(int[] arr, int i, int j) => (arr[i], arr[j]) = (arr[j], arr[i]);

static class Stats
{
    public static int Partitions, InsertionSorts, HeapSorts, MaxDepth;

    public static void Reset() => Partitions = InsertionSorts = HeapSorts = MaxDepth = 0;
}

The program is the previous implementation with counters in a static Stats class.

Run("all equal", new int[N]);
Run("10 distinct values", [.. Enumerable.Range(0, N).Select(_ => rnd.Next(10))]);

Besides random, sorted and reversed data, we sort arrays with many duplicates. A naive quicksort that puts elements equal to the pivot on one side degrades to O(n2) on such data.

The heap sort is never used. The depth limit for one million elements is 40, and median-of-three pivots keep the recursion much shallower. The fallback is a safety net for rare or malicious inputs. Sorted and equal data are split exactly in half, giving 65,536 partitions of at most 16 elements.

$ dotnet run
random             partitions  95,254  insertion sorts  93,831  heap sorts 0  max depth 22
sorted             partitions  65,535  insertion sorts  65,536  heap sorts 0  max depth 17
reversed           partitions 131,054  insertion sorts  65,536  heap sorts 0  max depth 31
all equal          partitions  65,535  insertion sorts  65,536  heap sorts 0  max depth 17
10 distinct values partitions  82,044  insertion sorts  82,045  heap sorts 0  max depth 17

The depth limit at work

To see the safety net in action, we need a quicksort that picks bad pivots. The next example uses the last element as the pivot, which is the worst choice for sorted data.

Program.cs
using System.Diagnostics;

const int N = 20_000;
int[] sorted = [.. Enumerable.Range(0, N)];

int[] a = [.. sorted];
Stats.Reset();
var sw = Stopwatch.StartNew();
QuickSort(a, 0, N - 1, int.MaxValue, 1);
Console.WriteLine($"quicksort:  {sw.ElapsedMilliseconds,4} ms, {Stats.Comparisons,11:N0} comparisons, depth {Stats.MaxDepth}");

int[] b = [.. sorted];
Stats.Reset();
sw.Restart();
QuickSort(b, 0, N - 1, 2 * (int.Log2(N) + 1), 1);
Console.WriteLine($"with limit: {sw.ElapsedMilliseconds,4} ms, {Stats.Comparisons,11:N0} comparisons, depth {Stats.MaxDepth}, heap sorts {Stats.HeapSorts}");

static void QuickSort(int[] arr, int lo, int hi, int depthLimit, int depth)
{
    if (lo >= hi) return;

    Stats.MaxDepth = Math.Max(Stats.MaxDepth, depth);

    if (depthLimit == 0)
    {
        Stats.HeapSorts++;
        HeapSort(arr, lo, hi);
        return;
    }

    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++)
    {
        Stats.Comparisons++;

        if (arr[j] < pivot)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
            i++;
        }
    }

    (arr[i], arr[hi]) = (arr[hi], arr[i]);

    QuickSort(arr, lo, i - 1, depthLimit - 1, depth + 1);
    QuickSort(arr, i + 1, hi, depthLimit - 1, depth + 1);
}

static void HeapSort(int[] arr, int lo, int hi)
{
    int n = hi - lo + 1;

    for (int i = n / 2 - 1; i >= 0; i--) SiftDown(arr, lo, i, n);

    for (int end = n - 1; end > 0; end--)
    {
        (arr[lo], arr[lo + end]) = (arr[lo + end], arr[lo]);
        SiftDown(arr, lo, 0, end);
    }
}

static void SiftDown(int[] arr, int lo, int i, int n)
{
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = left + 1;

        if (left < n && Greater(arr[lo + left], arr[lo + largest])) largest = left;
        if (right < n && Greater(arr[lo + right], arr[lo + largest])) largest = right;

        if (largest == i) return;

        (arr[lo + i], arr[lo + largest]) = (arr[lo + largest], arr[lo + i]);
        i = largest;
    }
}

static bool Greater(int x, int y)
{
    Stats.Comparisons++;
    return x > y;
}

static class Stats
{
    public static long Comparisons;
    public static int HeapSorts, MaxDepth;

    public static void Reset() => (Comparisons, HeapSorts, MaxDepth) = (0, 0, 0);
}

We sort 20,000 sorted numbers twice: without a depth limit and with the introsort limit.

int pivot = arr[hi];

On sorted data, the last element is the maximum. Each partition removes only one element, and the recursion depth grows with the length of the array.

QuickSort(b, 0, N - 1, 2 * (int.Log2(N) + 1), 1);

With the limit, the recursion stops at depth 30 and heap sort sorts the remaining partition in O(n log n) time.

The plain quicksort makes n2/2 comparisons, almost 200 million, and has 19,999 nested calls. A million sorted elements would need a million nested calls. With the depth limit, the sort needs about 177 times fewer comparisons.

$ dotnet run
quicksort:   776 ms, 199,990,000 comparisons, depth 19999
with limit:    6 ms,   1,127,711 comparisons, depth 31, heap sorts 1

Introsort vs Array.Sort

In the last example, we compare our implementation with Array.Sort on one million integers.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

const int N = 1_000_000;
var rnd = new Random(17);

Run("random", [.. Enumerable.Range(0, N).Select(_ => rnd.Next())]);
Run("sorted", [.. Enumerable.Range(0, N)]);
Run("reversed", [.. Enumerable.Range(0, N).Reverse()]);
Run("10 distinct values", [.. Enumerable.Range(0, N).Select(_ => rnd.Next(10))]);

static void Run(string name, int[] data)
{
    long t1 = Best(data, IntroSort);
    long t2 = Best(data, Array.Sort);

    Console.WriteLine($"{name,-18} IntroSort {t1,3} ms  Array.Sort {t2,3} ms");
}

static long Best(int[] data, Action<int[]> sort)
{
    long best = long.MaxValue;

    for (int i = 0; i < 5; i++)
    {
        int[] copy = [.. data];
        var sw = Stopwatch.StartNew();
        sort(copy);
        best = Math.Min(best, sw.ElapsedMilliseconds);
    }

    return best;
}

static void IntroSort(int[] arr)
{
    if (arr.Length < 2) return;

    int depthLimit = 2 * (int.Log2(arr.Length) + 1);
    Sort(arr, 0, arr.Length - 1, depthLimit);
}

static void Sort(int[] arr, int lo, int hi, int depthLimit)
{
    while (hi > lo)
    {
        int size = hi - lo + 1;

        if (size <= 16)
        {
            InsertionSort(arr, lo, hi);
            return;
        }

        if (depthLimit == 0)
        {
            HeapSort(arr, lo, hi);
            return;
        }

        depthLimit--;

        int p = Partition(arr, lo, hi);
        Sort(arr, p + 1, hi, depthLimit);
        hi = p - 1;
    }
}

static int Partition(int[] arr, int lo, int hi)
{
    int mid = lo + (hi - lo) / 2;

    if (arr[mid] < arr[lo]) Swap(arr, lo, mid);
    if (arr[hi] < arr[lo]) Swap(arr, lo, hi);
    if (arr[hi] < arr[mid]) Swap(arr, mid, hi);

    int pivot = arr[mid];
    Swap(arr, mid, hi - 1);

    int left = lo, right = hi - 1;

    while (left < right)
    {
        while (arr[++left] < pivot) { }
        while (pivot < arr[--right]) { }

        if (left >= right) break;

        Swap(arr, left, right);
    }

    if (left != hi - 1) Swap(arr, left, hi - 1);

    return left;
}

static void InsertionSort(int[] arr, int lo, int hi)
{
    for (int i = lo + 1; i <= hi; i++)
    {
        int key = arr[i];
        int j = i - 1;

        while (j >= lo && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

static void HeapSort(int[] arr, int lo, int hi)
{
    int n = hi - lo + 1;

    for (int i = n / 2 - 1; i >= 0; i--) SiftDown(arr, lo, i, n);

    for (int end = n - 1; end > 0; end--)
    {
        Swap(arr, lo, lo + end);
        SiftDown(arr, lo, 0, end);
    }
}

static void SiftDown(int[] arr, int lo, int i, int n)
{
    while (true)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = left + 1;

        if (left < n && arr[lo + left] > arr[lo + largest]) largest = left;
        if (right < n && arr[lo + right] > arr[lo + largest]) largest = right;

        if (largest == i) return;

        Swap(arr, lo + i, lo + largest);
        i = largest;
    }
}

static void Swap(int[] arr, int i, int j) => (arr[i], arr[j]) = (arr[j], arr[i]);

Each sort runs five times on a fresh copy and the best time is printed.

#:property PublishAot=false

File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.

Our implementation is about 10 percent slower than the built-in sort. The .NET version accesses the elements through references without bounds checks and handles partitions of two and three elements without a loop.

$ dotnet run -c Release benchmark.cs
random             IntroSort  67 ms  Array.Sort  60 ms
sorted             IntroSort   8 ms  Array.Sort   6 ms
reversed           IntroSort  15 ms  Array.Sort  13 ms
10 distinct values IntroSort  22 ms  Array.Sort  19 ms

Source

Array.Sort method
ArraySortHelper source code

In this article we have implemented the introsort algorithm in C#. See Array.Sort and Span.Sort for the built-in API.

Other sorting articles in C#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.