归并排序

=== "数组实现"
    
    ```cpp
    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]) {  // <!> 先判断 b[j] < a[i]，保证稳定性
          c[k] = b[j];
          ++j;
        } else {
          c[k] = a[i];
          ++i;
        }
        ++k;
      }
      // 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
      for (; i < aLen; ++i, ++k) c[k] = a[i];
      for (; j < bLen; ++j, ++k) c[k] = b[j];
    }
    ```

=== "指针实现"
    
    ```cpp
    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;
    }
    ```

也可使用 `<algorithm>` 库的 `merge` 函数，用法与上述指针式写法的相同。

```python
def merge(a, b):
    i, j = 0, 0
    c = []
    while(i < len(a) and j < len(b)):
        # <!> 先判断 b[j] < a[i]，保证稳定性
        if(b[j] < a[i]):
            c.append(b[j])
            j += 1
        else:
            c.append(a[i])
            i += 1
    # 此时一个数组已空，另一个数组非空，将非空的数组并入 c 中
    c.extend(a[i:])
    c.extend(b[j:])
    return c
```

```cpp
void merge_sort(int *a, int l, int r) {
  if (r - l <= 1) return;
  // 分解
  int mid = l + ((r - l) >> 1);
  merge_sort(a, l, mid), merge_sort(a, mid, r);
  // 合并
  int tmp[1024] = {};  // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
                       // vector；先将合并的结果放在 tmp 里，再返回到数组 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
    # 分解
    mid = (rr + ll) // 2
    merge_sort(a, ll, mid)
    merge_sort(a, mid, rr)
    # 合并
    a[ll:rr] = merge(a[ll:mid], a[mid:rr])
```

```cpp
void merge_sort(int *a, size_t n) {
  int tmp[1024] = {};  // 请结合实际情况设置 tmp 数组的长度（与 a 相同），或使用
                       // vector；先将合并的结果放在 tmp 里，再返回到数组 a
  for (size_t seg = 1; seg < n; seg <<= 1) {
    for (size_t left1 = 0; left1 < n - seg;
         left1 += seg + seg) {  // n - seg: 如果最后只有一个段就不用合并
      size_t right1 = left1 + seg;
      size_t left2 = right1;
      size_t right2 = std::min(left2 + seg, n);  // <!> 注意最后一个段的边界
      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
```