思路

  • 以数组中的中间位置为分界点（不用于快速排序将数值作为基准）
  • 递归得到左边排好序的序列 + 右边排好序的序列
  • 双指针法将左右两个序列合并成一个完整的有序序列（这一步是难点，也是重点）
    • 需要辅助数组temp，2个指针p1和p2，分别从左边序列a[left, mid]的起始位置和右边序列a[mid + 1, right]的起始位置出发，也就是从left和mid + 1出发
    • 将较小的数值顺序放入temp当中，如果a[p1] <= a[p2]，那么放入a[p1]，同时p1++。p2操作同理。
    • 将剩下的全部放入temp当中，如果p1序列有剩下的，那么，temp[k++] = a[p1++]。p2序列同理。此时的temp序列，已经是完整的有序序列了。
    • 将temp序列覆盖掉a[left, right]，完成归并。

      图示

      image.png
      Other.归并排序 - 图2
      image.png

      代码

      ```cpp

      include

      include

      using namespace std;

const int N = 1e5 + 10;

void merge_sort(int* nums, int left, int right) { if (left >= right) { return; }

  1. int mid = (left + right) / 2;
  2. merge_sort(nums, left, mid);
  3. merge_sort(nums, mid + 1, right);
  5. vector<int> temp(right - left + 2, 0);
  6. int p1 = left, p2 = mid + 1, k = 0;
  7. while (p1 <= mid && p2 <= right) {
  8.     if (nums[p1] <= nums[p2]) {
  9.         temp[k++] = nums[p1++];
  10.     } else {
  11.         temp[k++] = nums[p2++];
  12.     }
  13. }
  15. while (p1 <= mid) temp[k++] = nums[p1++];
  16. while (p2 <= right) temp[k++] = nums[p2++];
  18. for (int i = 0, j = left; j <= right; i++, j++) {
  19.     nums[j] = temp[i];
  20. }

}

int main() { int n = 0; cin >> n; int nums[N]; for (int i = 0; i < n; i++) { scanf(“%d”, &nums[i]);
} merge_sort(nums, 0, n - 1); for (int i = 0; i < n; ++i) { printf(“%d “, nums[i]); }

return 0;

} ```