为何我的Merge Sort代码在LeetCode超时，理论上本应更快？

我写了一段归并排序代码，本地运行正常，但在LeetCode等平台提交时出现「Time Limit Exceeded」错误。我知道归并排序性能应该优于选择排序、插入排序和冒泡排序，但这些简单排序算法在同一平台提交却不会超时。以下是我的代码：

#include<iostream>
#include<vector>
using namespace std;

void Merge(vector<int>& nums, int s, int e)
{
    int mid = (s+e)/2;
    int i=s,j=mid+1, MainIndex=s;

    vector<int>Merge;


    while(i<=mid && j<=e)                          
    {                                              
        if(nums[i]<nums[j])                         
        Merge.push_back(nums[i++]);                 

        else if(nums[i]>nums[j])
        Merge.push_back(nums[j++]);
    }

    while(j<=e)
    Merge.push_back(nums[j++]);

    while(i<=mid)
    Merge.push_back(nums[i++]);


    for (int i = 0; i < e-s+1; ++i)
    nums[MainIndex++] = Merge[i];
}

void MergeSort(vector<int>& nums, int s, int e)
{

    if(s>=e)
    return;

    int mid = (s+e)/2;

    MergeSort(nums,s,mid);
    MergeSort(nums,mid+1,e);

    Merge(nums,s,e);

}

vector<int> sortArray(vector<int>& nums)
{
    MergeSort(nums,0,nums.size()-1);
    return nums;
}


int main()
{
    vector<int> v = {4,1,3,7,5,9,2,6,8,0};

    cout<<"Before: ";
    for (int i = 0; i < v.size(); ++i)
    cout<<v[i]<<" ";

    v = sortArray(v);

    cout<<"\nAfter: ";
    for (int i = 0; i < v.size(); ++i)
    cout<<v[i]<<" ";
}

请问我的代码存在什么问题？还有哪些可以优化的地方？

代码存在的问题 #

• 未处理相等元素：Merge函数的第一个while循环只判断了nums[i]<nums[j]和nums[i]>nums[j]，漏掉了元素相等的情况。这会导致相等元素出现时，循环无法推进i或j，陷入死循环，直接触发超时。
• 频繁内存分配：每次调用Merge都新建vector<int> Merge，频繁的内存申请与释放会带来额外性能开销，处理大规模数据时该开销会被放大。
• mid计算有溢出风险：(s+e)/2的写法在s、e为较大整数时，会发生整数溢出，导致mid计算错误，破坏排序逻辑。

可优化的地方 #

1. 修复相等元素处理逻辑
   修改Merge函数的第一个循环条件，确保相等元素时也能推进指针：

   while(i<=mid && j<=e)
   {
       if(nums[i] <= nums[j])
           Merge.push_back(nums[i++]);
       else
           Merge.push_back(nums[j++]);
   }
   

2. 预分配辅助空间
   提前创建与原数组大小一致的辅助数组，避免每次Merge都新建vector，减少内存操作开销：

   void Merge(vector<int>& nums, vector<int>& temp, int s, int e)
   {
       int mid = s + (e - s)/2;
       int i=s, j=mid+1, k=s;
       while(i<=mid && j<=e)
       {
           if(nums[i] <= nums[j])
               temp[k++] = nums[i++];
           else
               temp[k++] = nums[j++];
       }
       while(i<=mid)
           temp[k++] = nums[i++];
       while(j<=e)
           temp[k++] = nums[j++];
       // 将临时数组内容复制回原数组
       for(int idx=s; idx<=e; idx++)
           nums[idx] = temp[idx];
   }
   
   void MergeSort(vector<int>& nums, vector<int>& temp, int s, int e)
   {
       if(s>=e) return;
       int mid = s + (e - s)/2;
       MergeSort(nums, temp, s, mid);
       MergeSort(nums, temp, mid+1, e);
       Merge(nums, temp, s, e);
   }
   
   vector<int> sortArray(vector<int>& nums)
   {
       vector<int> temp(nums.size());
       MergeSort(nums, temp, 0, nums.size()-1);
       return nums;
   }
   

3. 避免mid计算溢出
   用s + (e - s)/2替代(s+e)/2，从根本上避免整数相加溢出的问题。

4. 小数据量切换插入排序
   归并排序的递归开销在处理极小数组时会超过排序本身，设置阈值（如15），当子数组长度小于阈值时改用插入排序：

   void InsertionSort(vector<int>& nums, int s, int e)
   {
       for(int i=s+1; i<=e; i++)
       {
           int key = nums[i];
           int j = i-1;
           while(j>=s && nums[j]>key)
           {
               nums[j+1] = nums[j];
               j--;
           }
           nums[j+1] = key;
       }
   }
   
   void MergeSort(vector<int>& nums, vector<int>& temp, int s, int e)
   {
       if(e - s <= 15)
       {
           InsertionSort(nums, s, e);
           return;
       }
       int mid = s + (e - s)/2;
       MergeSort(nums, temp, s, mid);
       MergeSort(nums, temp, mid+1, e);
       Merge(nums, temp, s, e);
   }
   

5. 跳过已有序的子数组合并
   合并前判断左半部分最后一个元素是否小于等于右半部分第一个元素，若是则整个区间已有序，无需执行合并：

   void MergeSort(vector<int>& nums, vector<int>& temp, int s, int e)
   {
       if(e - s <= 15)
       {
           InsertionSort(nums, s, e);
           return;
       }
       int mid = s + (e - s)/2;
       MergeSort(nums, temp, s, mid);
       MergeSort(nums, temp, mid+1, e);
       // 已有序则跳过合并
       if(nums[mid] <= nums[mid+1])
           return;
       Merge(nums, temp, s, e);
   }
   

内容的提问来源于stack exchange，提问作者temporary singh