Merge Sort

Definition

Merge sort (merge sort) is an efficient stable comparison-based sorting algorithm.

Properties

Merge sort divides an array into segments, sorts them according to the divide-and-conquer strategy, and then merges them. Its time complexity is $\Theta (n \log n)$ in the best, worst, and average cases, and its space complexity is $\Theta (n)$.

Merge sort can use only $\Theta (1)$ auxiliary space, but for convenience it usually uses an auxiliary array with the same length as the original array.

Process

Merge

The most central part of merge sort is the merge process: merge two sorted arrays a[i] and b[j] into a sorted array c[k].

Enumerate a[i] and b[j] from left to right, select the smaller value, and put it into array c[k]; repeat this process until one of a[i] and b[j] is empty, then put the remaining elements of the other array into c[k].

To ensure stability, when the first element of the front segment is less than or equal to the first element of the back segment (a[i] <= b[j]), rather than only when it is less (a[i] < b[j]), it must be placed into c[k] as the smaller value.

Implementation

C/C++

Array Implementation

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]) {  // <!> Check b[j] < a[i] first to ensure stability
      c[k] = b[j];
      ++j;
    } else {
      c[k] = a[i];
      ++i;
    }
    ++k;
  }
  // At this point, one array is empty and the other is nonempty; merge the nonempty array into c
  for (; i < aLen; ++i, ++k) c[k] = a[i];
  for (; j < bLen; ++j, ++k) c[k] = b[j];
}

Pointer Implementation

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;
}

The <algorithm> library's merge function can also be used; its usage is the same as the pointer-style implementation above.

Python

def merge(a, b):
    i, j = 0, 0
    c = []
    while i < len(a) and j < len(b):
        # <!> Check b[j] < a[i] first to ensure stability
        if b[j] < a[i]:
            c.append(b[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
    # At this point, one array is empty and the other is nonempty; merge the nonempty array into c
    c.extend(a[i:])
    c.extend(b[j:])
    return c

Implementing Merge Sort with Divide and Conquer

1. When the array length is $1$, the array is already sorted and does not need to be decomposed further.

2. When the array length is greater than $1$, the array is probably not sorted. In this case, divide the array into two segments and check whether the two arrays are sorted separately (using item 1). If they are sorted, merge them into one sorted array; otherwise, repeat item 2 for the unsorted array and then merge them.

Mathematical induction can be used to prove that this process transforms an array into a sorted array.

To ensure the sorting complexity, the array is usually divided into two segments with lengths as equal as possible ($mid = \left\lfloor \dfrac{l + r}{2} \right\rfloor$).

Implementation

Note that the intervals represented by the following code are respectively $[l, r)$, $[l, mid)$, and $[mid, r)$.

C/C++

void merge_sort(int *a, int l, int r) {
  if (r - l <= 1) return;
  // Decompose
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // Merge
  int tmp[1024] = {};  // Set the length of the tmp array according to the actual situation (the same as a), or use
                       // vector; first put the merged result in tmp, then copy it back to array a
  merge(a + l, a + mid, a + mid, a + r, tmp + l);  // pointer-style merge
  for (int i = l; i < r; ++i) a[i] = tmp[i];
}

Python

def merge_sort(a, ll, rr):
    if rr - ll <= 1:
        return
    # Decompose
    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])

Implementing Merge Sort with Doubling

It is known that when the array length is $1$, the array is already sorted.

Cut the entire array into segments of length $1$.

From left to right, merge each pair of sorted segments of length $1$ in turn, producing a series of sorted segments of length $\le 2$;

Next, merge pairs of sorted segments of length $\le 2$ from left to right, producing a series of sorted segments of length $\le 4$;

Continue by merging, from left to right, pairs of sorted segments of length $\le 4$, producing a series of sorted segments of length $\le 8$;

……

Repeat the above process until only one sorted segment remains in the array; this segment is the sorted original array.

Why $\le n$ rather than $= n$

The array length is very likely not $2^x$; in that case, an incomplete segment may appear at the end, and the last segment may be independent.

Implementation

C/C++

void merge_sort(int *a, size_t n) {
  int tmp[1024] = {};  // Set the length of the tmp array according to the actual situation (the same as a), or use
                       // vector; first put the merged result in tmp, then copy it back to array a
  for (size_t seg = 1; seg < n; seg <<= 1) {
    for (size_t left1 = 0; left1 < n - seg;
         left1 += seg + seg) {  // n - seg: if there is only one segment left, no merge is needed
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> Note the boundary of the last segment
      merge(a + left1, a + right1, a + left2, a + right2,
            tmp + left1);  // pointer-style merge
      for (size_t i = left1; i < right2; ++i) a[i] = tmp[i];
    }
  }
}

Python

def merge_sort(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

Related reading and reference implementation: Inversions

An inversion is an ordered pair satisfying $i < j$ and $a_i > a_j$, namely $(i, j)$.

A sorted array has no inversions. During the merge operation of merge sort, whenever the first element of the back segment is selected as the current minimum, the total number of remaining elements in the front segment is the number of inversions removed by the merge operation. Therefore, the time complexity of using merge sort to count inversions is $\Theta (n \log n)$. In addition, inversions can also be counted with a Fenwick tree or a segment tree, with time complexity $O(n \log n)$; see the corresponding description in Fenwick Tree for a detailed explanation. Reference implementations of both algorithms are in the Inversions chapter.

External Links

• Merge Sort - GeeksforGeeks
• Merge Sort - Wikipedia, the Free Encyclopedia
• Inversions - Wikipedia, the Free Encyclopedia