Skip to content

Merge Sort

Definition

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

Properties

Merge sort is based on the divide-and-conquer approach, sorting the array segment by segment and then merging. 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 be implemented using only \(\Theta (1)\) auxiliary space, but for convenience, an auxiliary array of the same length as the original array is typically used.

Process

Merge

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

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

To ensure sorting 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 strictly less (a[i] < b[j]), it should be placed into c[k] as the minimum value.

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]) {  // <!> 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, the other is not. Append the non-empty array 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;
}

The merge function from the <algorithm> library can also be used, with the same usage as the pointer-style implementation 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):
        # <!> 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, the other is not. Append the non-empty array to c.
    c.extend(a[i:])
    c.extend(b[j:])
    return c

Divide and Conquer Implementation of Merge Sort

  1. When the array length is \(1\), the array is already sorted and does not need further decomposition.

  2. When the array length is greater than \(1\), the array is likely not sorted. In this case, split the array into two segments, and check if each segment is sorted (using step 1). If they are sorted, merge them into one sorted array; otherwise, repeat step 2 for the unsorted segment, then merge.

Using mathematical induction, it can be proven that this process transforms an array into a sorted array.

To ensure the complexity of the sort, the array is typically split into two segments of approximately equal length (\(mid = \left\lfloor \dfrac{l + r}{2} \right\rfloor\)).

Implementation

Note that the intervals represented by the code below are \([l, r)\), \([l, mid)\), and \([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;
  // Decompose
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // Merge
  int tmp[1024] = {};  // Please set the length of the tmp array according to the actual situation (same as a), or use
                       // vector; first store the merged result in tmp, then copy 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];
}

1
2
3
4
5
6
7
8
9
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])

Doubling Method Implementation of Merge Sort

It is known that when the array length is \(1\), the array is already sorted.

Split the entire array into segments of length \(1\).

From left to right, merge two sorted segments of length \(1\) to obtain a series of sorted segments with length \(\le 2\);

From left to right, merge two sorted segments of length \(\le 2\) to obtain a series of sorted segments with length \(\le 4\);

From left to right, merge two sorted segments of length \(\le 4\) to obtain a series of sorted segments with length \(\le 8\);

……

Repeat the above process until the array consists of only one sorted segment, which is the sorted original array.

Why \(\le n\) instead of \(= n\)?

The length of the array may not be a power of \(2\). In this case, the last segment may be incomplete, possibly resulting in an independent final segment.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void merge_sort(int *a, size_t n) {
  int tmp[1024] = {};  // Please set the length of the tmp array according to the actual situation (same as a), or use
                       // vector; first store the merged result in tmp, then copy 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's only one segment left, no need to merge
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> Pay attention to 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];
    }
  }
}

1
2
3
4
5
6
7
8
9
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

Inversion Pairs

Related reading and reference implementation: Inversion Pairs

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

A sorted array has no inversion pairs. During the merge operation of merge sort, each time the first element of the back segment is taken as the current minimum, the sum of the remaining elements in the front segment equals the number of inversion pairs reduced by that merge operation. Therefore, the time complexity for counting inversion pairs using merge sort is \(\Theta (n \log n)\). Additionally, inversion pair counting can also be solved using a Binary Indexed Tree (Fenwick Tree) or Segment Tree, with a time complexity of \(O(n \log n)\); a detailed explanation of this algorithm can be found in the corresponding section of Binary Indexed Tree. Reference implementations for both algorithms are provided in the Inversion Pairs section.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用