合并排序在不应该的时候比其他排序慢

Question

我写了一个合并排序代码，它在我的电脑上运行良好，但在 leetcode 等平台上出现“超过时间限制”错误。我听说归并排序比选择排序、插入排序或冒泡排序快，但它超过了时间限制，而其他排序则不在同一平台上。这是代码：

#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]<<" ";
}

我的代码有问题吗？还有什么需要优化的吗？

Answer 1

案例

nums[i] == nums[j]

没有处理，导致死循环

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

删除第二个

if

：

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