C++归并排序实现异常：无法定位代码错误

你的代码核心错误在于临时容器v的使用时机和逻辑完全错误，导致归并阶段没有用到递归排序后的有效数据，反而用了初始未排序的原始数据，最终只实现了数组两半的替换，而非排序合并。

错误原因拆解 #

当前代码的执行逻辑是：

1. 先把原数组的内容拷贝到临时容器v；
2. 递归排序原数组的左右半段；
3. 调用merge时，使用的是v的左右半段（这部分还是初始的未排序数据），直接覆盖了原数组里已经排好序的左右半段。

等于跳过了“合并两个已排序子数组”的核心步骤，反而把原数组的有序子段替换成了原始的无序数据。

修复后的代码（两种可行方案） #

方案一：先排序原数组的左右半段，再合并

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end){

  int num_elements = distance(range_begin, range_end);
  if( num_elements < 2){
    return;
  }

  // 先递归排序原范围的左右半部分
  RandomIt mid_it = range_begin + num_elements/2;
  MergeSort(range_begin, mid_it);
  MergeSort(mid_it, range_end);

  // 将已排序的原范围拷贝到临时容器
  vector<typename RandomIt::value_type> v(range_begin, range_end);
  // 合并两个已排序的子数组回原范围
  merge(begin(v), begin(v) + v.size()/2, begin(v) + v.size()/2, end(v), range_begin);
}

方案二：先拷贝到临时容器，排序临时容器的子段后合并回原数组

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end){

  int num_elements = distance(range_begin, range_end);
  if( num_elements < 2){
    return;
  }

  // 拷贝原数据到临时容器
  vector<typename RandomIt::value_type> v(range_begin, range_end);
  auto mid_v = begin(v) + num_elements/2;

  // 递归排序临时容器的左右半部分
  MergeSort(begin(v), mid_v);
  MergeSort(mid_v, end(v));

  // 将排序后的结果合并回原范围
  merge(begin(v), mid_v, mid_v, end(v), range_begin);
}

验证结果 #

运行你的main函数，两种方案都会输出正确的排序结果：

0 1 4 4 4 6 6 7 

内容的提问来源于stack exchange，提问作者Daniil Yefimov