四时宝库

归并排序（Merge Sort）是一种基于分治策略的高效排序算法。它将原始数组不断地分割成两个子数组，直到每个子数组只剩下一个元素为止（即基本有序），然后再通过合并已排序的子数组来最终得到完全有序的大数组。

以下是归并排序的主要步骤：

1. 分解（Divide）：将待排序的数组arr[L...R]递归地划分为两个相等（或接近相等）的部分，即arr[L...M]和arr[M+1...R]，其中M = (L + R) / 2是中间索引。

2. 解决（Conquer）：对划分后的两个子数组分别进行归并排序。这意味着对于左右两个子数组分别调用归并排序函数。

3. 合并（Combine）：当子数组被排序后，将它们合并回一个有序数组。合并过程通过比较两个子数组的元素，并按升序（或降序）将它们依次放入一个新的临时数组中，最后将临时数组的内容复制回原数组。

在C++中实现时，可以创建一个辅助函数merge()用于合并两个已排序的子数组，以及一个主函数mergeSort()负责递归地分解和合并数组。以下是简化版的C++代码框架：

void merge(std::vector<int>& arr, int left, int mid, int right) {
// 实现将arr[left...mid]与arr[mid+1...right]合并为有序序列的功能
}
void mergeSort(std::vector<int>& arr, int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;
    // 递归分解
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    // 合并已排序的子数组
    merge(arr, left, mid, right);
  }
}
// 使用示例
int main() {
  std::vector<int> nums = {5, 3, 8, 6, 7, 2, 1, 4};
  int n = nums.size();
  mergeSort(nums, 0, n - 1);
  // 输出排序后的数组
  for (int num : nums)
  std::cout << num << " ";
}

归并排序的时间复杂度为O(n log n)，并且由于其稳定的特性，在处理具有大量重复元素的数组时表现优秀。空间复杂度上，需要额外的空间与输入数组同样大小用于合并操作。