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:
- strictly descending runs are reversed in place,
- runs shorter than minrun (32 to 64 elements) are extended with binary insertion sort,
- runs are pushed on a stack and merged so that the merged runs have similar lengths,
- the merge uses galloping, an exponential search that copies long stretches from one run at once.
| Property | Value |
|---|---|
| Best case | O(n), already sorted or reversed data |
| Average and worst case | O(n log n) |
| Extra memory | O(n) |
| Stable | yes |
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.
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.
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.
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.
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.
#: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#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
- Array.Sort and Span.Sort
- Stable sorting
- Binary search
- Introsort
- Quickselect
- External sort
Author
List all C# tutorials.