ZetCode

C# Timsort

last modified November 15, 2026

In this article we implement natural merge sort and a simplified Timsort in C#. Both algorithms take advantage of order that already exists in the data. We detect sorted runs, merge them, show that the sort is stable, and measure where it beats Array.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.

Timsort algorithm

Real-world data is rarely random. Log files are almost sorted by time, a list gets a few new elements appended, two sorted lists are concatenated. A run is a sequence of elements that is already in order. A natural merge sort finds the runs and merges them, instead of splitting the data into halves blindly as the classic merge sort does.

Timsort, designed by Tim Peters for Python in 2002, is a refined natural merge sort:

PropertyValue
Best caseO(n), already sorted or reversed data
Average and worst caseO(n log n)
Extra memoryO(n)
Stableyes

Java uses Timsort to sort objects in Arrays.sort and List.sort, and so does Android. Python used it from 2002; since version 3.11, Python uses Powersort, which keeps Timsort's structure and changes the merge policy. .NET does not use Timsort; its in-place sorts are introsort.

Detecting runs

The first example splits an array into runs. Descending runs are reversed, so all runs end up ascending.

Program.cs
int[] nums = [3, 8, 12, 15, 9, 7, 4, 2, 5, 6, 6, 11, 10, 1];

int lo = 0;

while (lo < nums.Length)
{
    int len = CountRun(nums, lo);
    Console.WriteLine($"run at {lo,2}, length {len}: {string.Join(" ", nums[lo..(lo + len)])}");
    lo += len;
}

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

static int CountRun(int[] arr, int lo)
{
    int hi = lo + 1;

    if (hi == arr.Length) return 1;

    if (arr[hi++] < arr[lo])
    {
        while (hi < arr.Length && arr[hi] < arr[hi - 1]) hi++;
        Array.Reverse(arr, lo, hi - lo);
    }
    else
    {
        while (hi < arr.Length && arr[hi] >= arr[hi - 1]) hi++;
    }

    return hi - lo;
}

The CountRun method returns the length of the run that starts at index lo.

if (arr[hi++] < arr[lo])
{
    while (hi < arr.Length && arr[hi] < arr[hi - 1]) hi++;
    Array.Reverse(arr, lo, hi - lo);
}

If the second element is smaller than the first, the run is descending. It continues while each element is strictly smaller than the previous one. A strict comparison matters: reversing a run with two equal elements would swap them and break stability.

while (hi < arr.Length && arr[hi] >= arr[hi - 1]) hi++;

An ascending run may contain equal elements, such as the two sixes.

The array has four runs. The descending run 9 7 4 2 was reversed, and so was the short run 10 1 at the end.

$ dotnet run
run at  0, length 4: 3 8 12 15
run at  4, length 4: 2 4 7 9
run at  8, length 4: 5 6 6 11
run at 12, length 2: 1 10
3 8 12 15 2 4 7 9 5 6 6 11 1 10

Natural merge sort

A natural merge sort repeatedly finds the runs and merges neighboring pairs until a single run remains.

Program.cs
int[] nums = [3, 8, 12, 15, 9, 7, 4, 2, 5, 6, 6, 11, 10, 1];

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

static void NaturalMergeSort(int[] arr)
{
    int[] tmp = new int[arr.Length];

    while (true)
    {
        List<int> starts = [0];

        for (int i = 1; i < arr.Length; i++)
        {
            if (arr[i] < arr[i - 1]) starts.Add(i);
        }

        starts.Add(arr.Length);

        int runs = starts.Count - 1;
        Console.WriteLine($"runs {runs}: {string.Join(" | ", starts.Zip(starts.Skip(1), (a, b) => string.Join(" ", arr[a..b])))}");

        if (runs == 1) return;

        for (int r = 0; r + 1 < runs; r += 2)
        {
            Merge(arr, tmp, starts[r], starts[r + 1], starts[r + 2]);
        }
    }
}

static void Merge(int[] arr, int[] tmp, int lo, int mid, int hi)
{
    Array.Copy(arr, lo, tmp, lo, hi - lo);

    int i = lo, j = mid, k = lo;

    while (i < mid && j < hi)
    {
        arr[k++] = tmp[j] < tmp[i] ? tmp[j++] : tmp[i++];
    }

    while (i < mid) arr[k++] = tmp[i++];
    while (j < hi) arr[k++] = tmp[j++];
}

This simple version does not reverse descending runs; every element that is smaller than its predecessor starts a new run.

for (int i = 1; i < arr.Length; i++)
{
    if (arr[i] < arr[i - 1]) starts.Add(i);
}

We record the start of each run. The final entry, the array length, marks the end of the last run.

for (int r = 0; r + 1 < runs; r += 2)
{
    Merge(arr, tmp, starts[r], starts[r + 1], starts[r + 2]);
}

Each pass merges runs 0 and 1, 2 and 3, and so on. An odd run at the end is left for the next pass. Each pass halves the number of runs.

arr[k++] = tmp[j] < tmp[i] ? tmp[j++] : tmp[i++];

The element from the right run is taken only if it is strictly smaller. On a tie, the left element goes first, which keeps the merge stable.

The descending part 9 7 4 produces three one-element runs. That is why Timsort reverses descending runs. Sorted input is a single run and needs one pass with n - 1 comparisons.

$ dotnet run
runs 7: 3 8 12 15 | 9 | 7 | 4 | 2 5 6 6 11 | 10 | 1
runs 4: 3 8 9 12 15 | 4 7 | 2 5 6 6 10 11 | 1
runs 2: 3 4 7 8 9 12 15 | 1 2 5 6 6 10 11
runs 1: 1 2 3 4 5 6 6 7 8 9 10 11 12 15
1 2 3 4 5 6 6 7 8 9 10 11 12 15

Simplified Timsort

The next example implements Timsort without galloping. It prints each run and each merge. The data consists of six sorted blocks with lengths 80, 30, 200, 15, 120 and 60; each block is either ascending or descending.

Program.cs
var rnd = new Random(4);
List<int> data = [];

foreach (int len in new[] { 80, 30, 200, 15, 120, 60 })
{
    int[] run = [.. Enumerable.Range(0, len).Select(_ => rnd.Next(1_000_000)).Order()];
    data.AddRange(rnd.Next(2) == 0 ? run : run.Reverse());
}

int[] nums = [.. data];
Console.WriteLine($"n = {nums.Length}, minRun = {MinRunLength(nums.Length)}");

TimSort(nums, (a, b) => a.CompareTo(b));
Console.WriteLine($"sorted: {nums.SequenceEqual(data.Order())}");

static void TimSort<T>(T[] arr, Comparison<T> cmp)
{
    int n = arr.Length;
    if (n < 2) return;

    int minRun = MinRunLength(n);
    var runs = new List<(int Start, int Len)>();
    var tmp = new T[n];

    int lo = 0;

    while (lo < n)
    {
        int len = CountRunAndMakeAscending(arr, lo, cmp);
        int natural = len;

        if (len < minRun)
        {
            int force = Math.Min(minRun, n - lo);
            BinaryInsertionSort(arr, lo, lo + force, lo + len, cmp);
            len = force;
        }

        Console.WriteLine($"run [{lo}, {lo + len}), natural length {natural}");
        runs.Add((lo, len));
        MergeCollapse(arr, runs, tmp, cmp);
        lo += len;
    }

    while (runs.Count > 1)
    {
        int i = runs.Count - 2;
        if (i > 0 && runs[i - 1].Len < runs[i + 1].Len) i--;
        MergeAt(arr, runs, i, tmp, cmp);
    }
}

static int MinRunLength(int n)
{
    int r = 0;

    while (n >= 64)
    {
        r |= n & 1;
        n >>= 1;
    }

    return n + r;
}

static int CountRunAndMakeAscending<T>(T[] arr, int lo, Comparison<T> cmp)
{
    int hi = lo + 1;
    if (hi == arr.Length) return 1;

    if (cmp(arr[hi++], arr[lo]) < 0)
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) < 0) hi++;
        Array.Reverse(arr, lo, hi - lo);
    }
    else
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) >= 0) hi++;
    }

    return hi - lo;
}

static void BinaryInsertionSort<T>(T[] arr, int lo, int hi, int start, Comparison<T> cmp)
{
    for (int i = start; i < hi; i++)
    {
        T pivot = arr[i];
        int left = lo, right = i;

        while (left < right)
        {
            int mid = (left + right) >>> 1;

            if (cmp(pivot, arr[mid]) < 0) right = mid;
            else left = mid + 1;
        }

        Array.Copy(arr, left, arr, left + 1, i - left);
        arr[left] = pivot;
    }
}

static void MergeCollapse<T>(T[] arr, List<(int Start, int Len)> runs, T[] tmp, Comparison<T> cmp)
{
    while (runs.Count > 1)
    {
        int n = runs.Count - 2;

        if ((n > 0 && runs[n - 1].Len <= runs[n].Len + runs[n + 1].Len) ||
            (n > 1 && runs[n - 2].Len <= runs[n - 1].Len + runs[n].Len))
        {
            if (runs[n - 1].Len < runs[n + 1].Len) n--;
        }
        else if (runs[n].Len > runs[n + 1].Len)
        {
            break;
        }

        MergeAt(arr, runs, n, tmp, cmp);
    }
}

static void MergeAt<T>(T[] arr, List<(int Start, int Len)> runs, int i, T[] tmp, Comparison<T> cmp)
{
    var (start, len1) = runs[i];
    int len2 = runs[i + 1].Len;
    Console.WriteLine($"  merge [{start}, {start + len1}) with [{start + len1}, {start + len1 + len2})");

    runs[i] = (start, len1 + len2);
    runs.RemoveAt(i + 1);

    Array.Copy(arr, start, tmp, 0, len1);

    int a = 0, b = start + len1, k = start;
    int end = start + len1 + len2;

    while (a < len1 && b < end)
    {
        arr[k++] = cmp(arr[b], tmp[a]) < 0 ? arr[b++] : tmp[a++];
    }

    while (a < len1) arr[k++] = tmp[a++];
}

The method is generic and takes a Comparison<T>.

static int MinRunLength(int n)
{
    int r = 0;

    while (n >= 64)
    {
        r |= n & 1;
        n >>= 1;
    }

    return n + r;
}

The minimum run length is computed from the six most significant bits of n, plus one if any of the remaining bits is set. The result is between 32 and 64 and is chosen so that n / minRun is a power of two or slightly less, which makes the final merges balanced. Arrays shorter than 64 elements form a single run sorted by binary insertion sort.

if (len < minRun)
{
    int force = Math.Min(minRun, n - lo);
    BinaryInsertionSort(arr, lo, lo + force, lo + len, cmp);
    len = force;
}

A short natural run is extended to minRun elements. The first len elements are already sorted, so the insertion sort starts after them. It uses binary search to find the insertion point, which saves comparisons when they are expensive.

if (cmp(pivot, arr[mid]) < 0) right = mid;
else left = mid + 1;

The search finds the position after all elements equal to the pivot, so the insertion is stable.

if ((n > 0 && runs[n - 1].Len <= runs[n].Len + runs[n + 1].Len) ||
    (n > 1 && runs[n - 2].Len <= runs[n - 1].Len + runs[n].Len))
{
    if (runs[n - 1].Len < runs[n + 1].Len) n--;
}
else if (runs[n].Len > runs[n + 1].Len)
{
    break;
}

After a run is pushed, the stack is checked. The lengths of the runs on the stack must decrease faster than the Fibonacci numbers: each run must be longer than the next two together. If the rule is broken, two neighboring runs are merged. This keeps the stack short and the merges balanced. The check of the fourth run from the top fixes a bug found in 2015 in the Java and Python implementations by formal verification.

Array.Copy(arr, start, tmp, 0, len1);

The merge copies the left run to a temporary array and merges back into the original array. The right run stays in place.

The 30-element block forms a natural run of 31 elements, because the first element of the next block happens to continue it. The 15-element block is extended to 64 elements; the rest of the 120-element block, 71 elements, is the next run.

$ dotnet run
n = 505, minRun = 64
run [0, 80), natural length 80
run [80, 144), natural length 31
run [144, 310), natural length 166
  merge [0, 80) with [80, 144)
  merge [0, 144) with [144, 310)
run [310, 374), natural length 15
run [374, 445), natural length 71
  merge [310, 374) with [374, 445)
run [445, 505), natural length 60
  merge [310, 445) with [445, 505)
  merge [0, 310) with [310, 505)
sorted: True

Stability

Timsort is stable, which is the main reason why Java and Python use it for objects.

Program.cs
var rnd = new Random(3);
string[] cities = ["Bratislava", "Brno", "Vienna", "Krakow"];

Order[] orders = [.. Enumerable.Range(1, 100)
    .Select(id => new Order(id, cities[rnd.Next(cities.Length)]))];

Order[] a = [.. orders];
Array.Sort(a, (x, y) => string.CompareOrdinal(x.City, y.City));

Order[] b = [.. orders];
TimSort(b, (x, y) => string.CompareOrdinal(x.City, y.City));

Console.WriteLine($"Array.Sort, Brno ids: {string.Join(" ", a.Where(o => o.City == "Brno").Select(o => o.Id).Take(10))}");
Console.WriteLine($"TimSort, Brno ids:    {string.Join(" ", b.Where(o => o.City == "Brno").Select(o => o.Id).Take(10))}");

static void TimSort<T>(T[] arr, Comparison<T> cmp)
{
    int n = arr.Length;
    if (n < 2) return;

    int minRun = MinRunLength(n);
    var runs = new List<(int Start, int Len)>();
    var tmp = new T[n];

    int lo = 0;

    while (lo < n)
    {
        int len = CountRunAndMakeAscending(arr, lo, cmp);

        if (len < minRun)
        {
            int force = Math.Min(minRun, n - lo);
            BinaryInsertionSort(arr, lo, lo + force, lo + len, cmp);
            len = force;
        }

        runs.Add((lo, len));
        MergeCollapse(arr, runs, tmp, cmp);
        lo += len;
    }

    while (runs.Count > 1)
    {
        int i = runs.Count - 2;
        if (i > 0 && runs[i - 1].Len < runs[i + 1].Len) i--;
        MergeAt(arr, runs, i, tmp, cmp);
    }
}

static int MinRunLength(int n)
{
    int r = 0;

    while (n >= 64)
    {
        r |= n & 1;
        n >>= 1;
    }

    return n + r;
}

static int CountRunAndMakeAscending<T>(T[] arr, int lo, Comparison<T> cmp)
{
    int hi = lo + 1;
    if (hi == arr.Length) return 1;

    if (cmp(arr[hi++], arr[lo]) < 0)
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) < 0) hi++;
        Array.Reverse(arr, lo, hi - lo);
    }
    else
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) >= 0) hi++;
    }

    return hi - lo;
}

static void BinaryInsertionSort<T>(T[] arr, int lo, int hi, int start, Comparison<T> cmp)
{
    for (int i = start; i < hi; i++)
    {
        T pivot = arr[i];
        int left = lo, right = i;

        while (left < right)
        {
            int mid = (left + right) >>> 1;

            if (cmp(pivot, arr[mid]) < 0) right = mid;
            else left = mid + 1;
        }

        Array.Copy(arr, left, arr, left + 1, i - left);
        arr[left] = pivot;
    }
}

static void MergeCollapse<T>(T[] arr, List<(int Start, int Len)> runs, T[] tmp, Comparison<T> cmp)
{
    while (runs.Count > 1)
    {
        int n = runs.Count - 2;

        if ((n > 0 && runs[n - 1].Len <= runs[n].Len + runs[n + 1].Len) ||
            (n > 1 && runs[n - 2].Len <= runs[n - 1].Len + runs[n].Len))
        {
            if (runs[n - 1].Len < runs[n + 1].Len) n--;
        }
        else if (runs[n].Len > runs[n + 1].Len)
        {
            break;
        }

        MergeAt(arr, runs, n, tmp, cmp);
    }
}

static void MergeAt<T>(T[] arr, List<(int Start, int Len)> runs, int i, T[] tmp, Comparison<T> cmp)
{
    var (start, len1) = runs[i];
    int len2 = runs[i + 1].Len;
    runs[i] = (start, len1 + len2);
    runs.RemoveAt(i + 1);

    Array.Copy(arr, start, tmp, 0, len1);

    int a = 0, b = start + len1, k = start;
    int end = start + len1 + len2;

    while (a < len1 && b < end)
    {
        arr[k++] = cmp(arr[b], tmp[a]) < 0 ? arr[b++] : tmp[a++];
    }

    while (a < len1) arr[k++] = tmp[a++];
}

record Order(int Id, string City);

We sort 100 orders by city and print the first ten order ids from Brno.

The orders were created in the order of their ids. After Array.Sort, the Brno orders are mixed. After Timsort, they keep the order of their ids.

$ dotnet run
Array.Sort, Brno ids: 46 47 49 87 88 66 67 69 45 71
TimSort, Brno ids:    1 7 9 10 20 23 26 29 30 31

Timsort vs Array.Sort

In the last example, we sort one million records by an integer key with our Timsort, Array.Sort and OrderBy, on different kinds of input.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

const int N = 1_000_000;
var rnd = new Random(17);
int[] sorted = [.. Enumerable.Range(0, N)];

int[] nearly = [.. sorted];
for (int i = 0; i < N / 100; i++)
{
    int x = rnd.Next(N), y = rnd.Next(N);
    (nearly[x], nearly[y]) = (nearly[y], nearly[x]);
}

int[] sawtooth = [.. Enumerable.Range(0, N).Select(i => i % (N / 10))];

Run("random", [.. Enumerable.Range(0, N).Select(_ => rnd.Next())]);
Run("sorted", sorted);
Run("reversed", [.. sorted.Reverse()]);
Run("1% swapped", nearly);
Run("10 sorted runs", sawtooth);

static void Run(string name, int[] keys)
{
    Item[] data = [.. keys.Select((k, i) => new Item(k, i))];
    Comparison<Item> cmp = (x, y) => x.Key.CompareTo(y.Key);

    long t1 = Best(data, a => TimSort(a, cmp));
    long t2 = Best(data, a => Array.Sort(a, cmp));
    long t3 = Best(data, a => a.OrderBy(x => x.Key).ToArray());

    Console.WriteLine($"{name,-15} TimSort {t1,4} ms  Array.Sort {t2,4} ms  OrderBy {t3,4} ms");
}

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

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

    return best;
}

static void TimSort<T>(T[] arr, Comparison<T> cmp)
{
    int n = arr.Length;
    if (n < 2) return;

    int minRun = MinRunLength(n);
    var runs = new List<(int Start, int Len)>();
    var tmp = new T[n];

    int lo = 0;

    while (lo < n)
    {
        int len = CountRunAndMakeAscending(arr, lo, cmp);

        if (len < minRun)
        {
            int force = Math.Min(minRun, n - lo);
            BinaryInsertionSort(arr, lo, lo + force, lo + len, cmp);
            len = force;
        }

        runs.Add((lo, len));
        MergeCollapse(arr, runs, tmp, cmp);
        lo += len;
    }

    while (runs.Count > 1)
    {
        int i = runs.Count - 2;
        if (i > 0 && runs[i - 1].Len < runs[i + 1].Len) i--;
        MergeAt(arr, runs, i, tmp, cmp);
    }
}

static int MinRunLength(int n)
{
    int r = 0;

    while (n >= 64)
    {
        r |= n & 1;
        n >>= 1;
    }

    return n + r;
}

static int CountRunAndMakeAscending<T>(T[] arr, int lo, Comparison<T> cmp)
{
    int hi = lo + 1;
    if (hi == arr.Length) return 1;

    if (cmp(arr[hi++], arr[lo]) < 0)
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) < 0) hi++;
        Array.Reverse(arr, lo, hi - lo);
    }
    else
    {
        while (hi < arr.Length && cmp(arr[hi], arr[hi - 1]) >= 0) hi++;
    }

    return hi - lo;
}

static void BinaryInsertionSort<T>(T[] arr, int lo, int hi, int start, Comparison<T> cmp)
{
    for (int i = start; i < hi; i++)
    {
        T pivot = arr[i];
        int left = lo, right = i;

        while (left < right)
        {
            int mid = (left + right) >>> 1;

            if (cmp(pivot, arr[mid]) < 0) right = mid;
            else left = mid + 1;
        }

        Array.Copy(arr, left, arr, left + 1, i - left);
        arr[left] = pivot;
    }
}

static void MergeCollapse<T>(T[] arr, List<(int Start, int Len)> runs, T[] tmp, Comparison<T> cmp)
{
    while (runs.Count > 1)
    {
        int n = runs.Count - 2;

        if ((n > 0 && runs[n - 1].Len <= runs[n].Len + runs[n + 1].Len) ||
            (n > 1 && runs[n - 2].Len <= runs[n - 1].Len + runs[n].Len))
        {
            if (runs[n - 1].Len < runs[n + 1].Len) n--;
        }
        else if (runs[n].Len > runs[n + 1].Len)
        {
            break;
        }

        MergeAt(arr, runs, n, tmp, cmp);
    }
}

static void MergeAt<T>(T[] arr, List<(int Start, int Len)> runs, int i, T[] tmp, Comparison<T> cmp)
{
    var (start, len1) = runs[i];
    int len2 = runs[i + 1].Len;
    runs[i] = (start, len1 + len2);
    runs.RemoveAt(i + 1);

    Array.Copy(arr, start, tmp, 0, len1);

    int a = 0, b = start + len1, k = start;
    int end = start + len1 + len2;

    while (a < len1 && b < end)
    {
        arr[k++] = cmp(arr[b], tmp[a]) < 0 ? arr[b++] : tmp[a++];
    }

    while (a < len1) arr[k++] = tmp[a++];
}

record Item(int Key, int Id);

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

int[] sawtooth = [.. Enumerable.Range(0, N).Select(i => i % (N / 10))];

The sawtooth data consists of ten sorted runs of 100,000 elements, like ten sorted files concatenated.

On sorted and reversed data, Timsort finds a single run and finishes in a few milliseconds. On ten runs it needs only nine merges and is six times faster than Array.Sort. On random data, it is slower than both built-in sorts. With 1% of elements swapped, the runs are too short to help, and our version without galloping falls behind. Timsort pays off when the data is mostly made of long runs.

$ dotnet run -c Release benchmark.cs
random          TimSort  239 ms  Array.Sort  202 ms  OrderBy  148 ms
sorted          TimSort    1 ms  Array.Sort   24 ms  OrderBy   30 ms
reversed        TimSort    4 ms  Array.Sort   48 ms  OrderBy   50 ms
1% swapped      TimSort   76 ms  Array.Sort   31 ms  OrderBy   38 ms
10 sorted runs  TimSort   17 ms  Array.Sort  108 ms  OrderBy   83 ms

Source

listsort.txt, Tim Peters' description of Timsort
Array.Sort method

In this article we have implemented natural merge sort and a simplified Timsort in C#. See also stable sorting.

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.