Merge sort, step by step

• Merge sort, step by step
  • The code
  • Merging
  • Cost
  • When to choose it

§Merge sort, step by step

Merge sort is the classic divide and conquer sort.

1. Divide: split the array into two halves.
2. Conquer: sort each half, with merge sort again (recursion).
3. Combine: merge the two sorted halves into one sorted array.

An array of one item is already sorted, so the recursion stops there.

§The code

Console.WriteLine(string.Join(" ", Sort(new[] { 5, 2, 9, 1, 6 })));
static int[] Sort(int[] a)
{
    if (a.Length <= 1) return a;
    int[] left = Sort(a[..(a.Length / 2)]), right = Sort(a[(a.Length / 2)..]); // split in half
    var result = new List<int>(); int i = 0, j = 0;
    while (i < left.Length && j < right.Length) result.Add(left[i] <= right[j] ? left[i++] : right[j++]);
    result.AddRange(left[i..]); result.AddRange(right[j..]); // copy what is left
    return result.ToArray();
}

It prints 1 2 5 6 9.

§Merging

Look only at the front of each half and take the smaller item. Repeat until one half is empty, then copy what is left of the other. Using <= keeps equal items in their original order, so merge sort is stable.

§Cost

• Time: O(n log n) in every case. There are about log n levels of splitting, and each level merges n items in total.
• Memory: O(n) extra for the merged arrays.

§When to choose it

• You need a stable sort.
• You sort a linked list (merging needs no random access).
• The data is too big for memory and is sorted in chunks on disk (external sorting).

In everyday C#, Array.Sort is O(n log n) and the right default, but it is not stable; OrderBy in LINQ is stable. Know merge sort for interviews and for the cases above.

Read more: https://www.geeksforgeeks.org/dsa/merge-sort/

#tip · TIP-037