Merge Sort

What is merge sort?

A Divide and Conquer algorithm that divides the list in two sub-lists and calls itself onto them recursively till it can’t be split and merges them afterwards in a sorted manner.

Time and Space Complexities

• Best Time Complexity: O(n log(n))
• Average Time Complexity: O(n log(n))
• Worst Time Complexity: O(n log(n))
• Best Space Complexity: O(n)

Prerequisites

• Recursion

Steps

1. For an array of length ‘N’, split it into two halves(left and right subarrays) as evenly as possible.
2. Now, let’s take the left subarray and repeat the step 1 till we have sub arrays of length 1.
3. Start to merge the elements of the subarrays in the order they were split with the smallest digit placed at the start.
4. Repeat step 3 till the whole left array is sorted and merged.
5. Repeat steps 2, 3 and 4 for the right subarray.
6. Now take the two sorted subarrays and pick the first elements or both the subarrays, compare them and place the smallest one at the start.
7. Repeat step 6 for the proceeding elements.

Pseudo code

MergeSortedLists(LA, RA, A)
{
    nL = Length of LeftArray (LA)
    nR = Length of RightArray (RA)
    i = j = k = 0
    while(i<nL and j<nR)
    {
        if(LA[i] <= RA[j])
        {
            A[k] = LA[i]
            i = i+1
        }
        else
        {
            A[k] = RA[j]
            j = j+1
        }
        k = k+1
    }
    while(i<nL)
    {
        A[k] = LA[i]
        i = i+1
        k = k+1
    }
    while(j<nR)
    {
        A[k] = RA[j]
        j = j+1
        k = k+1
    }
}

MergeSort(A)
{
    n = length of Array (A)
    if(n<2)
        return
    mid = n/2
    left = array of size(mid)
    right = array of size(n-mid)
    for i = 0 to mid-1
        left[i] = A[i]
    for i = mid to n-1
        right[i-mid] = A[i]
    MergeSort(left)
    MergeSort(right)
    Merge(left, right, A)
}

Let’s Code

To code in any language other than C++, 👉 Click here 👈