Merge sort

Merge sort is the classic divide and conquer algorithm. It rests on one easy fact: merging two lists that are already sorted into one sorted list is fast. You only ever need to compare the two front items.

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

The recursion stops at pieces of one item, which are sorted by definition. Try the merge step first, then watch the whole sort:

The code

1static void MergeSort(int[] a)2{3    var buffer = new int[a.Length];          // one shared buffer: O(n) extra memory4    Sort(a, buffer, 0, a.Length - 1);5}6 7static void Sort(int[] a, int[] buffer, int lo, int hi)8{9    if (lo >= hi) return;                    // 0 or 1 item: already sorted10    int mid = lo + (hi - lo) / 2;11    Sort(a, buffer, lo, mid);                // sort the left half12    Sort(a, buffer, mid + 1, hi);            // sort the right half13    Merge(a, buffer, lo, mid, hi);           // combine14}15 16static void Merge(int[] a, int[] buffer, int lo, int mid, int hi)17{18    int i = lo, j = mid + 1, k = lo;19    while (i <= mid && j <= hi)20        buffer[k++] = a[i] <= a[j] ? a[i++] : a[j++];   // <= keeps it stable21    while (i <= mid) buffer[k++] = a[i++];              // leftovers22    while (j <= hi)  buffer[k++] = a[j++];23    Array.Copy(buffer, lo, a, lo, hi - lo + 1);         // copy back24}25 26int[] data = { 38, 27, 43, 3, 9, 82, 10, 1 };27MergeSort(data);28Console.WriteLine(string.Join(" ", data));

1 3 9 10 27 38 43 82

Why O(n log n)?

Draw the recursion as a tree. Each level splits every piece in half, so there are log₂ n levels. At every level, the merges together touch each of the n items once: O(n) work per level. Total: O(n) × log n = O(n log n). This holds for every input, sorted, reversed or random: merge sort has no bad case.

Where merge sort shines

• Guaranteed performance: no input can make it slow, which matters for real-time or safety-related code.
• Stability: sorting by several keys one after another works.
• Linked lists: merging relinks nodes, so it needs no extra buffer and no random access. It is the standard way to sort a linked list.
• Huge data (external sorting): sort chunks that fit in memory, write them to disk, then merge the sorted files. Databases do exactly this for big ORDER BY queries.

1static List<int> Union(int[] a, int[] b)2{3    var result = new List<int>();4    int i = 0, j = 0;5    while (i < a.Length || j < b.Length)6    {7        int v;8        if (j >= b.Length || (i < a.Length && a[i] < b[j])) v = a[i++];9        else if (i >= a.Length || b[j] < a[i]) v = b[j++];10        else { v = a[i]; i++; j++; }            // equal: take once11 12        if (result.Count == 0 || result[^1] != v)13            result.Add(v);14    }15    return result;16}17 18Console.WriteLine(string.Join(" ", Union([1, 3, 5, 7], [2, 3, 6, 7, 9])));

1 2 3 5 6 7 9