为何1亿元素的归并排序实现出现挂起？

问题描述 #

测试1亿元素的归并排序时程序挂起，堆排序处理相同规模耗时65秒，而归并排序处理1千万元素正常。怀疑问题出在int *arr= new int[size]这行代码，求排查思路。

实现代码 #

#include <iostream>
#include <cstdlib>
#include <time.h>
#include <fstream>

using namespace std;
void merge(int a[], int l, int m, int r)
{
    int i, j, k = l;
    int n1 = m - l + 1; // 数组1的元素个数
    int n2 = r - m;     // 数组2的元素个数
    int *L = new int[n1];
    int *R = new int[n2];

    for (i = 0; i < n1; i++)
        L[i] = a[l + i]; // 将待分割数组的元素复制到子数组
    for (j = 0; j < n2; j++)
        R[j] = a[m + j + 1];

    i = 0;
    j = 0;
    while (i < n1 && j < n2)
        if (L[i] < R[j])
            a[k++] = L[i++];
        else
            a[k++] = R[j++];
    while (i < n1)
        a[k++] = L[i++];
    while (j < n2)
        a[k++] = R[j++];
}
void mergeSort(int a[], int l, int r)
{
    if (l < r)
    {
        int m = (l + r) / 2;    // 找到中间元素进行分割
        mergeSort(a, l, m);     // 分割左半部分
        mergeSort(a, m + 1, r); // 分割右半部分
        merge(a, l, m, r);      // 合并
    }
}
int main()
{

    int size;
    cout << "请输入随机数组的元素个数: ";
    cin >> size;
    int *arr = new int[size];
    srand(time(0));
    for (int i = 0; i < size; i++)
    {
        arr[i] = rand() % 2000000000;
    }

    mergeSort(arr, 0, size - 1);
    cout << "done!";
    return 0;
}

排查思路 #

1. 内存泄漏与内存耗尽（最可能原因） #

• merge函数中每次分配L和R临时数组后未执行delete，归并排序的临时内存总开销是**O(n log n)**级别。1亿元素的情况下，累计分配的int总数约为2.7亿×4字节=10.8GB，远超常规内存容量，会导致系统频繁进行磁盘交换（swap），程序因此挂起。
• 解决：在merge函数末尾添加delete[] L; delete[] R;释放临时内存；或预先分配全局临时数组，避免反复动态分配内存。

2. 初始数组内存分配验证 #

• 1亿个int占400MB，64位程序下堆内存可容纳，但32位程序受限于4GB虚拟内存上限可能分配失败。可添加判断：

  int *arr = new (nothrow) int[size];
  if (!arr) {
      cerr << "内存分配失败" << endl;
      return 1;
  }
  

  确认是否因内存分配失败导致异常。

3. 递归栈溢出（可能性极低） #

• 归并排序递归深度为log2(1e8)≈27层，远低于默认栈大小（通常为几MB），栈溢出概率极低，可排除。

4. 随机数生成性能优化 #

• rand()生成1亿个随机数本身耗时，但堆排序可正常运行，因此不是挂起主因。可替换为std::mt19937提升随机数生成效率：

  #include <random>
  // ...
  std::mt19937 rng(time(0));
  std::uniform_int_distribution<int> dist(0, 1999999999);
  for (int i = 0; i < size; i++) {
      arr[i] = dist(rng);
  }
  

内容的提问来源于stack exchange，提问作者Anh Tuan