Merge Sort

Given an array of integers nums, sort the array in ascending order.

Algorithm

Merge-Sort-Tutorial

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Code

class Solution
{
public:
    void merge(vector<int> &nums, int start, int mid, int end)
    {
        vector<int> la;
        vector<int> ra;

        for (int i = start; i <= mid; i++)
        {
            la.push_back(nums[i]);
        }

        for (int i = mid + 1; i <= end; i++)
        {
            ra.push_back(nums[i]);
        }

        int i = 0, j = 0, k = start;
        while (i < la.size() && j < ra.size())
        {

            if (la[i] <= ra[j])
            {
                nums[k] = la[i];
                i++;
            }
            else
            {
                nums[k] = ra[j];
                j++;
            }
            k++;
        }

        while (i < la.size())
        {
            nums[k] = la[i];
            i++;
            k++;
        }

        while (j < ra.size())
        {
            nums[k] = ra[j];
            j++;
            k++;
        }
        return;
    }

    void mergeSort(vector<int> &nums, int start, int end)
    {

        if (start >= end)
        {
            return;
        }

        int mid = (start + end) / 2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);
        merge(nums, start, mid, end);
        return;
    }

    vector<int> sortArray(vector<int> &nums)
    {

        int n = nums.size();
        mergeSort(nums, 0, n - 1);
        return nums;
    }
};

Time complexity of Merge Sort is θ(nLogn) in all 3 cases (worst, average and best)