Pseudo Code For Merge Sort – Simplified in 3 Steps

In Data Structures and Algorithms, you might have heard about merge sort. But understanding the pseudo code for merge sort could be complex.

In this blog, I will talk about the implementation of merge sort,

And show you the pseudo code for it, which you can use to implement merge sort in any programming language.

Merge sort has two parts: the recursion logic and the merge logic. In this blog, I will explain them. Then we will combine them and understand the pseudo code for merge sort.

Let’s jump right into the discussion of merge sort and finally come up with the pseudo code.

Break Down Of Merge Sort

Merge sort is one of the sorting algorithms used in data structures and algorithms that are widely used because of it’s less time complexity.

Merge sort has two parts: the merge function, and the recursive merge sort function.

The merge function can merge 2 sorted arrays. The recursive merge sort function divides the array into 2 parts,

Then sort them and merge (conquer) them.

The merge function merges 2 sorted arrays. In the merge function, we need to ensure that the sorting is stable and efficient.

Let’s start by understanding the merge function used in merge sort.

merge function – Merge Two Sorted Arrays

The merge function used in the merge sort algorithm is pretty straightforward.

You have two sorted arrays. When you merge them, you will take care of two index variables – i and j.

i tracks the elements of the first array, while j tracks the elements of the second array.

i and j both start from the index 0. We compare the elements at i and j. When we see that the element at i is less than or equal to the element at j, we pick the value present at i.

Sorting will be stable only if, we use the equality sign in the condition. Otherwise, it is not guaranteed that the sorting will be stable.

Another case would be where the element at j is greater than the element at I, In that case, we will pick the element at j.

Now there’s another scenario –

While traversing, one array is completely traversed,

While some of the other array elements are remaining.

If that happens, we have to copy the other array that are remaining.

The pseudo code for the above logic is as follows –

void merge(a[], b[], m, n)
{
    i = 0, j = 0;
    while (i < m && j < n)
    {
        if (a[i] <= b[j])
        {
            print a[i];
            i++;
        }
        else
        {
            print b[j];
            j++;
        }
    }

    while (i < m)
    {
        print a[i];
        i++;
    }

    while (j < n)
    {
        print b[j];
        j++;
    }
}

On a side note, why does this merge algorithm always work?

Because we are working with two sorted arrays,

In array a, any value after i is greater than equal to a[i]

And in array b any value after j is greater than equal to b[j]. 

So if a[i] is less than or equal to a[j], it means a[i] is less than or equal to every value after b[j].

This makes sure that after the merging the result array is still sorted.

Here we have taken 2 separate sorted arrays. But in merge sort, we need to sort only one array.

So let’s try to understand the logic of the merge function in one array only.

Merge In One Array

Merge sort follows the logic of divide and conquer. Divide the array into separate parts and then merge these two parts. We assume that the two parts are sorted and then use the merge function.

If we want to merge the two divided parts that are sorted, we need to take care of three variables – low, mid and high. 

low to mid is one array and from mid+1 to high is another array. Both arrays are sorted.

If I want to write the merge logic for this kind of situation then the pseudo code will look something like this –

merge(a[], low, mid, high)
{
    n1 = mid - low + 1;
    n2 = high - mid;
    left[n1], right[n2];
    for (i = 0; i < n1; i++)
        left[i] = a[low + i];
    for (i = 0; i < n2; i++)
        right[i] = a[mid + i + 1];

    i = 0, j = 0, k = low;
    while (i < n1 && j < n2)
    {
        if (left[i] <= right[j])
        {
            a[k] = left[i];
            i++;
            k++;
        }
        else
        {
            a[k] = right[j];
            j++;
            k++;
        }
    }

    while (i < n1)
    {
        a[k] = left[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        a[k] = right[j];
        j++;
        k++;
    }
}

The code looks pretty much the same as the previous code.

The only difference that you can see here is, that we are creating 2 separate arrays left and right from the array a. We know that the left and right arrays are sorted. Then we just have to calculate the size of these two arrays n1 and n2.

Everything else will stay the same. Here we have to remember the low value is not always going to be 0. So, when calculating the values for n1, we add the value of low to get the next index and we start k from low.

This is the merge function we will be using for our merge sort.

Now let’s take a look at the divide and conquer approach that merges sort uses.

Pseudo Code For Merge Sort

The recursive solution for merge sort is very intuitive.

If we understand the merge function,

Then understanding the rest of the merge sort algorithm is pretty simple.

We need to make the merge function work. For the merge function to work, we need 2 sorted arrays.

From one array a – we divide the array into 2 parts, then sort both the divided parts.

Then call the merge function to merge them.

What is the baseline of this recursive solution?

When we have an array with one element, we know that it is sorted, so we will return.

In every recursive call, we calculate the mid value. We recursively call for merge sort from low to mid and then mid+1 to high to sort the divided parts.

Then, we will get 2 sorted arrays. After that, we can call the merge function with the low, mid, and high,

And merge the two sorted arrays from low to mid and mid+1 to high.

The pseudo code for the merge sort is as follows –

mergeSort(a[], l, h)
{
    if (l < h) // atleast 2 elements
    {
        m = l + (h - l) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, h);
        merge(a, l, m, h);
    }
}

See how easy merge sort is if you understand the merge function!

You can use this pseudo code to write merge sort in any programming language.

For more visual understanding of the merge sort, watch this video –

Conclusion

In this blog, we discussed merge sort in detail. We also looked into different parts of the merge sort algorithm. 

We started with the merge function, which is the heart of the merge sort,

Then we dived into the merge sort algorithm which uses divide and conquer.

Want to learn more about data structures and algorithms? Read my next blog where I talk about memorization in dynamic programming.