Skip to content

Merge Sort

This page introduces merge sort and its use for counting inversions.

Definition

Merge sort is an efficient, stable, comparison-based sorting algorithm.

Properties

Merge sort is based on divide and conquer: it splits the array into segments, sorts them, and merges them. It runs in \(\Theta (n \log n)\) in the best case, the worst case and the average case, and its space complexity is \(\Theta (n)\).

Merge sort can get by with only \(\Theta (1)\) auxiliary space, but for convenience it usually uses an auxiliary array as long as the original one.

Procedure

Merge

The heart of merge sort is the merge step: combining two sorted arrays a and b into one sorted array c.

Iterate over a[i] and b[j] from left to right, each time writing the smaller element to c[k]. When one array is exhausted, append the remaining elements of the other to c.

To keep the sort stable, the head of the first segment must go into c[k] as the minimum whenever it is less than or equal to the head of the second segment (a[i] <= b[j]), not only when it is strictly less (a[i] < b[j]).

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void merge(const int* a, size_t aLen, const int* b, size_t bLen, int* c) {
  size_t i = 0, j = 0, k = 0;
  while (i < aLen && j < bLen) {
    if (b[j] < a[i]) {  // <!> test b[j] < a[i] first, to keep the sort stable
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // one array is now exhausted and the other is not: append what is left of it to c
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void merge(const int* aBegin, const int* aEnd, const int* bBegin,
           const int* bEnd, int* c) {
  while (aBegin != aEnd && bBegin != bEnd) {
    if (*bBegin < *aBegin) {
      *c = *bBegin;
      ++bBegin;
    } else {
      *c = *aBegin;
      ++aBegin;
    }
    ++c;
  }
  for (; aBegin != aEnd; ++aBegin, ++c) *c = *aBegin;
  for (; bBegin != bEnd; ++bBegin, ++c) *c = *bBegin;
}

You can also use the std::merge function of the <algorithm> library. It is called in the same way as the pointer version above.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def merge(a, b):
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        # <!> test b[j] < a[i] first, to keep the sort stable
        if b[j] < a[i]:
            c.append(b[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
    # one array is now exhausted and the other is not: append what is left of it to c
    c.extend(a[i:])
    c.extend(b[j:])
    return c

Top-down merge sort

  1. An array of length \(1\) is already sorted and does not need to be split any further.
  2. An array of length greater than \(1\) is quite likely not sorted. Split it into two segments and check whether each of the two arrays is sorted (using rule 1). If they are, merge them into one sorted array; otherwise, apply rule 2 again to each array that is not yet sorted, and then merge.

By induction, this procedure turns any array into a sorted array.

To guarantee the complexity of the sort, the array is usually split into two segments whose lengths are as equal as possible (\(\textit{mid} = \left\lfloor \dfrac{l + r}{2} \right\rfloor\)).

Implementation

Note that the ranges in the code below are \([l, r)\), \([l, \textit{mid})\) and \([\textit{mid}, r)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void merge_sort(int* a, int l, int r) {
  if (r - l <= 1) return;
  // divide
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid);
  merge_sort(a, mid, r);
  // merge
  std::vector<int> tmp(r - l);  // allocate a buffer only for the range merged in this call
  merge(a + l, a + mid, a + mid, a + r, tmp.data());
  for (int i = l; i < r; ++i) a[i] = tmp[i - l];
}
1
2
3
4
5
6
7
8
9
def merge_sort(a, ll, rr):
    if rr - ll <= 1:
        return
    # divide
    mid = (rr + ll) // 2
    merge_sort(a, ll, mid)
    merge_sort(a, mid, rr)
    # merge
    a[ll:rr] = merge(a[ll:mid], a[mid:rr])

Bottom-up merge sort

We know that an array of length \(1\) is already sorted.

Cut the whole array into segments of length \(1\).

Going from left to right, merge the sorted runs of length \(1\) two at a time. This gives a series of sorted runs of length \(\le 2\).

Going from left to right, merge the sorted runs of length \(\le 2\) two at a time. This gives a series of sorted runs of length \(\le 4\).

Going from left to right, merge the sorted runs of length \(\le 4\) two at a time. This gives a series of sorted runs of length \(\le 8\).

...

Repeat this until the array consists of a single sorted run. That segment is the original array, sorted.

Why \(\le\) and not \(=\)

The length of the array is quite likely not \(2^x\). In that case the last segment may be shorter than the others, and it may also be left on its own, with no segment to merge with.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void merge_sort(int* a, size_t n) {
  std::vector<int> tmp(n);  // the merge buffer is as long as the input
  for (size_t seg = 1; seg < n; seg <<= 1) {
    for (size_t left1 = 0; left1 < n - seg;
         left1 += seg + seg) {  // n - seg: if only one segment is left at the end, there is nothing to merge
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> mind the boundary of the last segment
      merge(a + left1, a + right1, a + left2, a + right2,
            tmp.data() + left1);  // pointer-style merge
      for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
    }
  }
}
1
2
3
4
5
6
7
8
9
def merge_sort_iterative(a):
    seg = 1
    while seg < len(a):
        for l1 in range(0, len(a) - seg, seg + seg):
            r1 = l1 + seg
            l2 = r1
            r2 = l2 + seg
            a[l1:r2] = merge(a[l1:r1], a[l2:r2])
        seg <<= 1

Inversions

Further reading and reference implementations: inversions

An inversion is an ordered pair \((i, j)\) with \(i < j\) and \(a_i > a_j\).

A sorted array has no inversions. During a merge, each time the head of the second segment is taken out as the current minimum, count the elements remaining in the first segment; the sum of these counts is the number of inversions the merge removes. Merge sort therefore counts inversions in \(\Theta (n \log n)\). Inversions can also be counted with a Fenwick tree or a segment tree, again in \(O(n \log n)\); for a detailed explanation of that algorithm, see the corresponding part of Fenwick tree. Reference implementations of both algorithms are in the inversions section.