Sorting Algorithms 1: Insertion Sort, Merge Sort and Stability

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

Bookstore's order list comes from the database sorted by date. The customer service screen wants to group this list by customer name; a developer writes Array.Sort(orders, byCustomer). The team assumes each customer's orders will still show up in date order on screen; after all, the list was already sorted by date.

Is that assumption right? Second question: is it faster to sort a 10,000-element, nearly sorted price list (only 1 percent of it swapped) with insertion sort, which is O(n²), or with Array.Sort, which is O(n log n)?

Selection and Bubble Sort: Only for Comparison

The textbooks' first two sorting algorithms are almost never used in production, but they are worth a short look to see what is better and why:

namespace Algorithms.Sorting;

public static class SimpleSorts
{
    // n^2/2 comparisons whatever the input; at most n-1 swaps. Not stable.
    public static void SelectionSort<T>(Span<T> items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        for (int i = 0; i < items.Length - 1; i++)
        {
            int min = i;
            for (int j = i + 1; j < items.Length; j++)
                if (comparer.Compare(items[j], items[min]) < 0) min = j;
            (items[i], items[min]) = (items[min], items[i]);
        }
    }

    // stops early when a pass makes no swap. Stable.
    public static void BubbleSort<T>(Span<T> items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        for (int end = items.Length - 1; end > 0; end--)
        {
            bool swapped = false;
            for (int j = 0; j < end; j++)
            {
                if (comparer.Compare(items[j], items[j + 1]) <= 0) continue;
                (items[j], items[j + 1]) = (items[j + 1], items[j]);
                swapped = true;
            }
            if (!swapped) return;
        }
    }
}

Selection sort finds the smallest item of the remaining part on each pass and moves it to the front. It makes n²/2 comparisons even if the input is already sorted; its only advantage is at most n − 1 swaps, which matters only where writes are very expensive. Because it swaps distant elements, it is not stable. Bubble sort compares and swaps neighbours; thanks to the early exit it finishes in one pass on sorted input, but in general it is the slowest of all the O(n²) algorithms. In this series we use both only as references in tests.

Insertion Sort: Still Valuable on Small and Nearly Sorted Data

Insertion sort works like sorting the playing cards in your hand: the left part is always sorted; you take the next element and drop it into the right place by shifting the larger ones one step to the right.

// shifts larger items right and drops the current one into the gap. Stable, in place.
// Nearly sorted input: each item moves only a little, total work close to n.
public static void InsertionSort<T>(Span<T> items, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    for (int i = 1; i < items.Length; i++)
    {
        T current = items[i];
        int j = i - 1;
        // strict > keeps equal items in their original order: this is what makes it stable
        while (j >= 0 && comparer.Compare(items[j], current) > 0)
        {
            items[j + 1] = items[j];
            j--;
        }
        items[j + 1] = current;
    }
}

In the worst case (reverse-sorted input) every element shifts all the way: O(n²). But the accurate cost is O(n + number of inversions), an inversion being a pair of elements in the wrong order. In a nearly sorted list the number of inversions is small and insertion sort runs in almost linear time. On small n its constants are so low that it beats complex algorithms: no extra memory, no recursion, sequential memory access. That is why .NET's Array.Sort switches to insertion sort for partitions of 16 elements or fewer; the Remarks section on Microsoft Learn says so explicitly.

Merge Sort: Split, Sort, Merge

Merge sort is the textbook example of divide and conquer: split the array in two, sort both halves recursively, and merge the two sorted halves in a single pass. In the series' third post we wrote MergeSorted, which merges two sorted linked lists; the array version is the same idea.

namespace Algorithms.Sorting;

public static class MergeSort
{
    public static void TopDown<T>(T[] items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        T[] buffer = new T[items.Length]; // the O(n) extra memory, allocated once
        Sort(items, buffer, 0, items.Length, comparer);
    }

    private static void Sort<T>(T[] items, T[] buffer, int lo, int hi, IComparer<T> comparer)
    {
        if (hi - lo < 2) return;                 // 0 or 1 item: already sorted
        int mid = lo + (hi - lo) / 2;
        Sort(items, buffer, lo, mid, comparer);  // [lo, mid)
        Sort(items, buffer, mid, hi, comparer);  // [mid, hi)
        if (comparer.Compare(items[mid - 1], items[mid]) <= 0) return; // halves already in order
        Merge(items, buffer, lo, mid, hi, comparer);
    }

    public static void BottomUp<T>(T[] items, IComparer<T>? comparer = null)
    {
        comparer ??= Comparer<T>.Default;
        T[] buffer = new T[items.Length];
        // merge runs of 1, then 2, then 4...: no recursion at all
        for (int width = 1; width < items.Length; width *= 2)
        {
            for (int lo = 0; lo < items.Length - width; lo += 2 * width)
            {
                int mid = lo + width;
                int hi = Math.Min(lo + 2 * width, items.Length);
                Merge(items, buffer, lo, mid, hi, comparer);
            }
        }
    }

    private static void Merge<T>(T[] items, T[] buffer, int lo, int mid, int hi, IComparer<T> comparer)
    {
        Array.Copy(items, lo, buffer, lo, hi - lo);
        int left = lo, right = mid;
        for (int k = lo; k < hi; k++)
        {
            if (left == mid) items[k] = buffer[right++];
            else if (right == hi) items[k] = buffer[left++];
            // <= : on a tie the left (earlier) item wins, so equal items keep their order: stable
            else if (comparer.Compare(buffer[left], buffer[right]) <= 0) items[k] = buffer[left++];
            else items[k] = buffer[right++];
        }
    }
}

At each level of the tree n elements are merged in total, and there are log₂ n levels: n log n. That holds whatever the input. Merge sort's best, average and worst cases are the same; unlike quick sort it has no bad input. Deriving this result from the recurrence is in the Big-O and Complexity series post "Deriving Time Complexity from Code". The early exit in Sort (no merge needed if the last element of the left half is not greater than the first of the right half) is a small but effective optimization: it brings merge sort down to O(n) on sorted input.

The price is O(n) extra memory: buffer. The top-down version's recursion depth is log₂ n, that is 20 frames for 1 million elements; the stack overflow worry from the series' fifth post does not apply. The bottom-up version removes recursion entirely: it merges neighbouring runs of width 1, 2, 4, ... in a loop. Both give the same result and the tests check it:

[Theory]
[MemberData(nameof(Algorithms))]
public void Sort_RandomAndEdgeInputs_MatchesArraySort(string name)
{
    Random random = new(11);
    int[][] inputs =
    [
        [], [1], [2, 1], [5, 5, 5],
        [.. Enumerable.Range(0, 100)],
        [.. Enumerable.Range(0, 100).Reverse()],
        [.. Enumerable.Range(0, 1_000).Select(_ => random.Next(50))],
        [.. Enumerable.Range(0, 777).Select(_ => random.Next())],
    ];
    foreach (int[] input in inputs)
    {
        int[] expected = [.. input];
        Array.Sort(expected);
        int[] actual = [.. input];

        Run(name, actual);

        Assert.Equal(expected, actual);
    }
}

The inputs were chosen deliberately: empty array, one element, two elements, all equal, sorted, reverse-sorted, many duplicates (1,000 numbers between 0 and 49) and a length that is not a power of two (777, which tests bottom-up's last, incomplete run). Most sorting bugs hide in these edge cases.

A relative of merge sort is widely used on big data: external merge sort. To sort a 50 GB order log that does not fit in memory, you split the file into chunks that fit, sort each chunk separately and write it to disk as a "run"; then you read all the runs at the same time and merge them into one sorted file by picking the smallest head at each step. That is how databases run an ORDER BY larger than memory. The way to pick the smallest head of k runs quickly is a min-heap; we will see it in the series' heap post.

Measuring: Small, Random and Nearly Sorted

The benchmark measures three algorithms at three sizes on two kinds of input. Nearly sorted input is produced by swapping 1 percent of positions in a sorted list with their neighbour, like a sorted list in which a few prices changed. Each measurement first copies the source array into a working array; the copy cost is the same for all three algorithms.

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    | 16    | random        |         35.077 ns |  1.00 |         - |
| Insertion    | 16    | random        |         50.678 ns |  1.45 |         - |
| MergeTopDown | 16    | random        |         91.259 ns |  2.60 |      88 B |
|              |       |               |                   |       |           |
| ArraySort    | 1000  | random        |      6,732.024 ns |  1.01 |         - |
| Insertion    | 1000  | random        |    145,942.100 ns | 21.79 |         - |
| MergeTopDown | 1000  | random        |     14,383.555 ns |  2.15 |    4024 B |
|              |       |               |                   |       |           |
| ArraySort    | 10000 | random        |    190,747.053 ns |  1.01 |         - |
| Insertion    | 10000 | random        | 16,098,611.987 ns | 85.24 |         - |
| MergeTopDown | 10000 | random        |    394,038.485 ns |  2.09 |   40024 B |
|              |       |               |                   |       |           |
| ArraySort    | 10000 | nearly-sorted |     34,182.605 ns |  1.00 |         - |
| Insertion    | 10000 | nearly-sorted |      5,755.829 ns |  0.17 |         - |
| MergeTopDown | 10000 | nearly-sorted |     21,309.086 ns |  0.62 |   40024 B |

On random input the table is as expected: insertion sort collapses as n grows; at 10,000 elements it is 85 times slower than Array.Sort. N grew 10 times and insertion sort's time grew 110 times, quadratic growth. Merge sort stays around twice Array.Sort and allocates n elements of extra memory (4 bytes per int, 40,024 bytes for 10,000).

On nearly sorted input the table flips, and here is the answer to the second question: O(n²) insertion sort is 6 times faster than Array.Sort. In 10,000 elements only 100 neighbouring pairs were swapped; insertion sort goes back at most one step per element and the work is close to n comparisons. Merge sort also beats Array.Sort thanks to its early exit. Introsort has no check that notices the input is already sorted and keeps partitioning. At 16 elements Array.Sort already runs insertion sort; our version is somewhat slower because the BCL (Base Class Library) has a specialized path for primitive types such as int that makes no comparer calls. The measurements ran while other work was running on the machine; look at the ratios.

Stability: the Order of Equal Elements

A sorting algorithm is stable if it keeps the input order of elements that compare as equal. When sorting numbers it does not matter; you cannot tell one 5 from another. When sorting objects by one field, the order of the other fields depends exactly on this property. Let's run the opening scenario: 200 orders arrive sorted by date, and we sort them by customer first with Array.Sort, then with merge sort:

Array.Sort by customer (first 5 orders of 'ada'):
  #200 ada    2026-12-06
  # 29 ada    2026-10-10
  #140 ada    2026-11-16
  #136 ada    2026-11-15
  #132 ada    2026-11-14
MergeSort by customer (first 5 orders of 'ada'):
  #  8 ada    2026-10-03
  #  9 ada    2026-10-04
  # 29 ada    2026-10-10
  # 33 ada    2026-10-12
  # 41 ada    2026-10-14

The opening assumption is wrong. Array.Sort gathered Ada's orders together, but the date order between them was lost: the December order comes first. Microsoft Learn states it plainly: Array.Sort performs an unstable sort, and the order of equal elements might not be preserved; List<T>.Sort uses the same algorithm. In merge sort, the <= in the merge takes the left element first on ties and the date order is kept. LINQ's (Language Integrated Query) OrderBy and ThenBy are stable, and their documentation guarantees it. The tests pin down the three stable ways and the unstable one on the same data:

private static readonly Comparer<Order> ByCustomer = Comparer<Order>.Create((a, b) => string.CompareOrdinal(a.Customer, b.Customer));

private static bool DatesInOrderWithinCustomer(IReadOnlyList<Order> sorted) =>
    sorted.Zip(sorted.Skip(1)).All(p => p.First.Customer != p.Second.Customer || p.First.Date <= p.Second.Date);

[Fact]
public void ArraySort_ByCustomer_LosesDateOrder()
{
    Order[] orders = SampleOrders.Create(200); // already sorted by date

    Array.Sort(orders, ByCustomer);

    Assert.False(DatesInOrderWithinCustomer(orders));
}

[Fact]
public void StableSorts_ByCustomer_KeepDateOrder()
{
    Order[] merge = SampleOrders.Create(200);
    MergeSort.TopDown(merge, ByCustomer);
    Order[] insertion = SampleOrders.Create(200);
    SimpleSorts.InsertionSort<Order>(insertion, ByCustomer);
    List<Order> linq = [.. SampleOrders.Create(200).OrderBy(o => o.Customer, StringComparer.Ordinal)];

    Assert.True(DatesInOrderWithinCustomer(merge));
    Assert.True(DatesInOrderWithinCustomer(insertion));
    Assert.True(DatesInOrderWithinCustomer(linq));
    Assert.Equal(linq, merge);
}

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

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

The sneaky part of this bug is that it does not show on small data. With 16 or fewer orders Array.Sort uses insertion sort, and because insertion sort is stable the order is kept; the 10-order customer list in the test environment looks right, the 200-order list in production breaks. That is why we picked 200 elements for the test data.

The right fix is one of two options: state all the sort criteria explicitly (OrderBy(o => o.Customer).ThenBy(o => o.Date), or a comparer that compares both fields), or rely on a stable sort. The first is more robust; whoever reads the code sees what the order is based on, and it does not depend on the order of the input. Why a comparer must be consistent and transitive was covered in the C# Collections series post "Sorted Collections in C#: SortedList, SortedDictionary, SortedSet and IComparer".

In Production

Do not put your own sorting algorithm in production. Array.Sort, List<T>.Sort, MemoryExtensions.Sort and LINQ's Order/OrderBy have been optimized for years. The real value of the algorithms in this post is knowing which one to choose when: LINQ or an explicit multi-field comparer when you need stability, external merge sort or the database when the data is larger than memory.

LINQ's stable sort has a price: OrderBy produces a new sequence and keeps the keys in a separate array; it allocates more than the in-place Array.Sort. If you sort a large list on every request on a hot path, measure the difference.

Treat nearly sorted data as a special case. A sorted list updated continuously with small changes (price updates, a leaderboard) can be maintained by moving the changed element to the right place (a single insertion sort step, or BinarySearch + Insert) instead of re-sorting from scratch every time.

Common Pitfalls

Assuming Array.Sort is stable. If the test data has fewer than 16 elements the bug does not show; with production data the order breaks at random. If the order of elements with equal keys matters, either put all criteria in the comparer or use OrderBy/ThenBy.

Writing < instead of <= in the merge. Taking the right element first on ties silently makes merge sort unstable. Since the result is still sorted, an ordinary sorting test will not catch it; you need a separate stability test.

A non-strict comparison in insertion sort. >= instead of > also shifts equal elements and breaks stability.

Forgetting merge sort's memory on big data. Sorting 100 million long values with merge sort needs a second 800 MB buffer; this kind of extra memory is what pushes a container over its memory limit.

A Small Experiment

★☆☆ Change the <= in Merge to < and run the tests. Which test breaks, and which keeps passing? Does this show why stability must be tested separately?

★★☆ Add the "switch to insertion sort on small subarrays" optimization to merge sort: call InsertionSort when hi - lo <= 16. How does the time on random input change in the benchmark? Try thresholds of 8 and 32 too.

★★★ Simulate data that does not fit in memory: split 1,000,000 random orders into 10 files, sort each file separately, then produce a single sorted file with a k-way merge that reads the 10 files at the same time. For now, use a simple loop to pick the smallest head at each step; in the series' heap post we will replace it with a PriorityQueue.

Merge sort is n log n in every case but needs extra memory. In the next post we look at quick sort, which sorts in place and is usually the fastest in practice, at introsort, which keeps it from dropping to O(n²) on bad input, and at counting and radix sort, which sort without comparing: how exactly does .NET's Array.Sort sort?