为何我的3-way merge sort实现无法处理长度大于4的数组？

核心问题分析 #

代码无法处理长度超过4的数组，根源在于子数组分区计算错误：

• 在merge_sort函数中，p1和p2直接用size/3、2*size/3计算，得到的是相对于数组全局起始位置（0）的偏移，而非当前子数组的start位置偏移。
• 递归处理非起始位置的子数组时，这种计算会导致分区区间完全无效（比如出现start > end的错误递归调用），部分子数组未被排序，最终整体排序失败。

修复方案 #

1. 修正子数组分区计算 #

将merge_sort中的p1和p2改为基于当前子数组的start位置计算，确保分区区间在当前子数组范围内：

int size = end - start + 1;
int p1 = start + size / 3;  // 第二个分区的起始索引
int p2 = start + 2 * size / 3;  // 第三个分区的起始索引

2. 修复后的完整代码 #

#include <iostream>

void merge(int arr[], int start, int p1, int p2, int end);

void merge_sort(int arr[], int start, int end) {
  if (start >= end)
    return;

  if (end == start + 1) {
    if (arr[start] > arr[end]) {
      std::swap(arr[start], arr[end]);
    }
    return;
  }

  int size = end - start + 1;
  int p1 = start + size / 3;
  int p2 = start + 2 * size / 3;

  merge_sort(arr, start, p1 - 1);
  merge_sort(arr, p1, p2 - 1);
  merge_sort(arr, p2, end);

  merge(arr, start, p1, p2, end + 1);
}

void merge(int arr[], int start, int p1, int p2, int end) {
  int n = end - start;
  int* temp = new int[n];

  int j = start;
  int k = p1;
  int l = p2;
  int i = 0;

  // 同时遍历三个有序区间，取最小元素
  while (j < p1 && k < p2 && l < end) {
    if (arr[j] <= arr[k] && arr[j] <= arr[l]) {
      temp[i++] = arr[j++];
    } else if (arr[k] <= arr[j] && arr[k] <= arr[l]) {
      temp[i++] = arr[k++];
    } else {
      temp[i++] = arr[l++];
    }
  }

  // 处理剩余的两个区间
  while (j < p1 && k < p2) {
    temp[i++] = (arr[j] <= arr[k]) ? arr[j++] : arr[k++];
  }
  while (j < p1 && l < end) {
    temp[i++] = (arr[j] <= arr[l]) ? arr[j++] : arr[l++];
  }
  while (k < p2 && l < end) {
    temp[i++] = (arr[k] <= arr[l]) ? arr[k++] : arr[l++];
  }

  // 处理最后剩余的单个区间
  while (j < p1) temp[i++] = arr[j++];
  while (k < p2) temp[i++] = arr[k++];
  while (l < end) temp[i++] = arr[l++];

  // 将临时数组内容复制回原数组
  for (i = 0; i < n; ++i) {
    arr[start + i] = temp[i];
  }

  delete[] temp;
}

int main() {
  int size;
  std::cout << "Enter the size of array:";
  std::cin >> size;

  int* mohit = new int[size];
  std::cout << "Enter the elements of the array:";
  for (int m = 0; m < size; ++m) {
    std::cin >> mohit[m];
  }

  merge_sort(mohit, 0, size - 1);

  std::cout << "The final sorted array is:" << std::endl;
  for (int count = 0; count < size; ++count) {
    std::cout << mohit[count] << " ";
  }
  std::cout << std::endl;

  delete[] mohit;
  return 0;
}

额外优化说明 #

• 将原merge函数中复杂的分支剩余元素处理拆分为多个独立循环，降低逻辑复杂度，避免遗漏边界情况。
• 使用std::swap简化两元素交换代码，提升可读性。
• 调整比较条件为<=，保证排序的稳定性（可根据需求改为<）。

内容的提问来源于stack exchange，提问作者Mohit Bansal