Magic Bookof Algorithms
/
DE

SortingSRT-02

Merge Sort

Halve until nothing is left to do, then merge everything back in order.

Running time
O(n log n)
Worst case
O(n log n)
Extra memory
O(n)
Stable
yes

01What it is about

Merge Sort is the textbook example of divide and conquer: a big problem is halved until the pieces are trivial, and the solutions are put back together afterwards.

The algorithm is predictably fast. It always needs O(n log n) steps, even in the worst case. In exchange it needs extra memory, because merging creates a new array.

3827433982
382743
3982
3927384382
The list is split, each half is sorted on its own and both are merged afterwards.

02How it works

The process consists of two halves.

Divide. The array is split in the middle and both halves are sorted in exactly the same way. This recursion ends as soon as a part consists of a single element only, because that is sorted by definition.

Merge. Two already sorted halves are easy to combine: you only ever look at the front element of both halves, take the smaller one and move forward there. Every element is touched exactly once.

Halving creates log n levels, and on each level every element is copied once. Together that gives the n ยท log n steps.

03Implementation

MagicBook.Algorithms/Sorting/MergeSort.csC#
public static class MergeSort
{
    // Returns a new sorted array and leaves the input untouched.
    public static int[] Sort(int[] numbers)
    {
        // An array with zero or one element is sorted by definition - this stops the recursion.
        if (numbers.Length <= 1)
            return numbers;

        var middle = numbers.Length / 2;

        // Split in the middle and sort both halves in exactly the same way.
        var left = Sort(numbers[..middle]);
        var right = Sort(numbers[middle..]);

        return Merge(left, right);
    }

    // Walks through both sorted halves at once and always takes the smaller front element.
    private static int[] Merge(int[] left, int[] right)
    {
        var merged = new int[left.Length + right.Length];
        var leftIndex = 0;
        var rightIndex = 0;

        for (var i = 0; i < merged.Length; i++)
        {
            var takeFromLeft = rightIndex >= right.Length
                || (leftIndex < left.Length && left[leftIndex] <= right[rightIndex]);

            merged[i] = takeFromLeft ? left[leftIndex++] : right[rightIndex++];
        }

        return merged;
    }
}

04Example

MagicBook.Console/Examples/MergeSortExample.csC#
var numbers = new[] { 38, 27, 43, 3, 9, 82, 10 };

var sorted = MergeSort.Sort(numbers);

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

// The input array is not modified.
Console.WriteLine(string.Join(", ", numbers));
Console output
3, 9, 10, 27, 38, 43, 82
38, 27, 43, 3, 9, 82, 10

05Good to know

  • Merge Sort is stable as long as a tie takes the element from the left half first. That is exactly what the <= in the comparison is for.
  • Because it reads the data sequentially, it also works for amounts of data that do not fit into memory.
  • The variant here returns a new array and leaves the input untouched. That reads nicely but costs memory.