Merge sort working slower than other sorts when it should'nt be

Question

I wrote a Merge sort code, which works fine in my pc but give "Time Limit Exceeded" error on platforms like leetcode. I have heard that merge sort is faster than Selection, Insertion or Bubble sort, yet, it exceeds time limit while other sorts don't at the same platforms. Here is the code:

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

Am I doing something wrong with the code? Is there something more to be optimized?

Answer 1

The case nums[i] == nums[j] is not handled, which causes an infinite loop.

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

Remove the second if:

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