Merge Sort Pseudocode in C, C++, Java, and Python

How does Merge Sort work?

Merge Sort is a popular comparison-based sorting algorithm that follows the divide-and-conquer paradigm. Here's how it works:

Divide: The unsorted list is divided into two halves, roughly equal in size, until each sublist contains only one element. This is done recursively.

Conquer: Then, the individual elements are treated as sorted, as a list with one element is inherently sorted.

Merge: The algorithm then starts merging the sublists. It compares the elements from both sublists and combines them into a new, sorted list. This process continues until there is only one sorted list.

Example:

Original unsorted list: [38, 27, 43, 3, 9, 82, 10]

1. Divide: Split into two sublists: [38, 27, 43] and [3, 9, 82, 10].
2. Divide: Further split the first sublist into [38] and [27, 43].
3. Divide: Continue splitting the second sublist into [3, 9] and [82, 10].
4. Conquer: Merge [38] and [27] into [27, 38].
5. Conquer: Merge [3] and [9] into [3, 9].
6. Conquer: Merge [82] and [10] into [10, 82].
7. Merge: Merge [27, 38] and [43] into [27, 38, 43].
8. Merge: Merge [3, 9] and [10, 82] into [3, 9, 10, 82].
9. Merge: Merge [27, 38, 43] and [3, 9, 10, 82] into the final sorted list: [3, 9, 10, 27, 38, 43, 82].

Merge Sort is efficient and stable, with a time complexity of O(n log n) in the worst and average cases, making it suitable for sorting large datasets. It also does not depend on the initial order of elements, which makes it useful for many applications.

Merge Sort Pseudocode

As we know, merge sort works on the divide and conquer approach. It repeatedly divides the array into smaller parts until it is left with a single element. Now let us see the pseudocode of merge sort. 

Step 1: Declare the variable low and high to mark the start and end of the array.

Step 2: Low will equal 0, and high will equal array size -1. 

Step 3: Calculate mid using low + high / 2.

Step 4: Call the mergeSort function on the part (low, mid) and (mid+1, high).

Step 5: This calling will continue till low<high is satisfied.

Step 6: Finally, call the merge function to merge these two halves.

Merge Sort Algorithm

Merge sort is easy to implement, but you should have a sound knowledge of recursion. Recursion is very important to implement the merge sort. As mentioned earlier in the definition, the merge sort has two main parts: the first is to break down the array into smaller parts, effectively called smaller subarrays.

The second one is to merge the subarrays, assumed to be sorted(we know the assumption is true as The Principle of Mathematical Induction, PMI comes to rescue. Read the blog on Recursion and Backtracking Algorithm With Practice Problem to learn more) to get the final sorted array. 

So we will create two functions. The first function will recursively divide the array into smaller subarrays, and another function will merge it back, effectively merging the two sorted arrays.
 

The algorithm of merge sort is as follows.

mergeSort(arr, size)
If  size > 1
 
Step 1: Find the size of the leftSubArray and rightSubArray so that we can divide the array into two-part
leftSize = size / 2;
rightSize = size - leftSize;
 
Step 2: Call the mergesort for the leftSubArray 
mergeSort(leftSubArray, leftSize);
 
Step 3: Call the mergesort for the rightSubArray
mergeSort(rightSubArray, rightSize);
 
Step 4: Call the merge function to merge these two halves       mergeTwoSortedArray(leftSubArray, rightSubArray, arr,
leftSize, rightSize)

Merge sort Algorithm Dry Run

Merge sort is a divide-and-conquer algorithm. It works by recursively dividing the array into two halves, sorting each half, and then merging the sorted halves back together.

Below are the steps of a dry run of merge sort on the array [1, 5, 3, 2, 4, 0]:

1. Divide the array into two halves: `[1, 5]` and `[3, 2, 4, 0]`
    
2. Recursively sort each half
    
3. Merge the sorted halves back together: `[0, 1, 2, 3, 4, 5]`

Time Complexity of Merge Sort 

The time complexity of merge sort is O(n log n), where n is the number of elements in the array. This is because the merge sort algorithm divides the array into two halves at each recursive step, and the number of recursive steps is log n.

Space Complexity of Merge sort 

The space complexity of merge sort is O(n), where n is the number of elements in the array. This is because the merge sort algorithm needs to create a temporary array to store the merged subarrays. The size of the temporary array can be equal to the size of the original array.

Merge sort in C

Below is the implementation of the merge sort algorithm in C.

• C

C

#include <stdio.h>
// Function to merge left and right subarrays of arr.
void mergeTwoSortedArray(int leftSubArray[], int rightSubArray[], int arr[], int n, int m) {
 // i is for leftSubArray, j is for rightSubArray, k is for arr
 int i = 0;
 int j = 0;
 int k = 0;
 while (i < n && j < m) {
   if (leftSubArray[i] <= rightSubArray[j]) {
     arr[k] = leftSubArray[i];
     i++;
   } else {
     arr[k] = rightSubArray[j];
     j++;
   }
   k++;
 }
 // copy remaining elements of leftSubArray[]
 while (i < n) {
   arr[k] = leftSubArray[i];
   i++;
   k++;
 }
 // copy remaining elements of rightSubArray
 while (j < m) {
   arr[k] = rightSubArray[j];
   j++;
   k++;
 }
}
void mergeSort(int arr[], int size) {
 // this is a special case - it means we don't have an array to sort. Mind that the array size can never be less than 0
 if (size == 0) {
   return;
 }
 // if only one element is present in arr then we don't need to divide array further as one element is sorted in itself.
 if (size == 1) {
   return;
 }
 // create leftSubArray and rightSubArray - and copy the elements as it is from arr.
 int n = size / 2;
 int m = size - n;
 int leftSubArray[n];
 int rightSubArray[m];
 // pointer for arr
 int k = 0;
 for (int i = 0; i < n; i++) {
   leftSubArray[i] = arr[k];
   k++;
 }
 for (int j = 0; j < m; j++) {
   rightSubArray[j] = arr[k];
   k++;
 }
 // call mergeSort on left subarray
 mergeSort(leftSubArray, n);
 // call mergeSort on right subarray
 mergeSort(rightSubArray, m);
 // merging the two sorted subarrays back to the original one
 mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m);
}
int main() {
 int arr[] = {
   14,
   17,
   22,
   4,
   1,
   5
 };
 int n = sizeof(arr) / sizeof(arr[0]);
 mergeSort(arr, n);
 printf("Sorted array: ");
 for (int i = 0; i < n; i++) {
   printf("%d ", arr[i]);
 }
 printf("\n");
 return 0;
}

You can also try this code with Online C Compiler

Run Code

Output

Sorted array: 1 4 5 14 17 22 

Merge sort in C++

Below is the implementation of the merge sort algorithm in C++.

• C++

C++

#include <iostream>
using namespace std;


// Function to merge left and right subarrays of arr.
void mergeTwoSortedArray(int leftSubArray[], int rightSubArray[], int arr[], int n, int m)
{
    // i is for leftSubArray, j is for rightSubArray, k is for arr
     int i = 0;
     int j = 0;
     int k = 0;



    while (i < n && j < m) {
        if (leftSubArray[i] <= rightSubArray[j]) {
            arr[k] = leftSubArray[i];
            i++;
        }
        else {
            arr[k] = rightSubArray[j];
            j++;
        }
        k++;
    }


    // copy remaining elements of leftSubArray[] 
    while (i < n) {
        arr[k] = leftSubArray[i];
        i++;
        k++;
    }


    // copy remaining elements of rightSubArray
    while (j < m) {
        arr[k] = rightSubArray[j];

        j++;
        k++;
    }
   
     
}



void mergeSort(int arr[], int size){
//this is a special case - it means we don't have an array to sort. Mind that the array size can never be less than 0
if (size == 0) {
return;
}


     // if only one element is present in arr then we don't need to divide array further as one element is sorted in itself.
       if(size == 1)
       {
         return;
       }
    // create leftSubArray and rightSubArray - and copy the elements as it is from arr.
        int n  = size / 2;
        int m = size - n;


        int leftSubArray[n];
        int rightSubArray[m];
        
   //pointer for arr
        int k = 0;


        for(int i = 0; i < n; i++)
        {
            leftSubArray[i] = arr[k];
            k++;
        }

       for(int j = 0; j < m; j++)
        {
            rightSubArray[j] = arr[k];
            k++;
        }
    
     //call mergeSort on left subarray
        mergeSort(leftSubArray, n);
    
     //call mergeSort on right subarray
        mergeSort(rightSubArray, m);
    
     //merging the two sorted subarrays back to the original one
        mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m);
        return;
}


int main()
{
    int arr[] = { 14, 17, 22, 4, 1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr,n);
    
    cout<<"Sorted array: ";
    for(int i = 0; i < n; i++)
    {
         cout<<arr[i]<<" ";
    }
   
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Sorted array: 1 4 5 14 17 22

Time Complexity

The recurrence relation for merge sort algorithm can be written as :

 T(n)  =  2T(n / 2)  +  θ(n) 

This recurrence relation can be solved by the recurrence tree or master theorem. The recurrence tree for the above relation can be drawn as:

Image source: researchgate.net

We are dividing the array into two parts at each step till each subarray contains only one element, so the number of levels in this tree would be log₂n, and at these different levels, while merging back the array, we will at max compare n elements. So the time complexity of the merge sort is θ(n*log₂n).

The time complexity of Merge Sort in worst, average, and best case is θ(n*log₂n)  as merge sort always divides the array into two halves regardless of the fact that what is the present state of the array and takes linear time to merge the array.

Space complexity: The space complexity of the above code is O(n) as we are using an auxiliary array to copy the left and right subarray. But if you are asked by the interviewer to consider the stack memory then we are having a maximum of log₂n function calls waiting in the stack which yields an extra space complexity of O(log₂n). So total space complexity becomes O(n+log₂n) as n is greater than log₂n, we ignore the log₂n part.

There is another space-optimized approach to implement the merge sort called in-place merge sort in which instead of copying an array in left and right subarray we divide an array with help of pointers logically creating division in the original array by specifying the window for every recursive call. We shift the elements of the array to finally achieve the sorted configuration. 

Thus taking no extra space and having O(1) space complexity. But if you are asked by the interviewer to consider the stack memory then we have log₂n function calls waiting in the stack memory and hence leads to O(log₂n) space complexity.

We have discussed all the technicalities of merge sort and also implemented it. You should try to implement the merge sort on Coding Ninjas Studio. 

Coding Ninjas Studio is a platform developed by some aspiring enthusiasts and working professionals who have experience in companies like Google, Amazon, Microsoft. At Coding Ninjas Studio you get interview problems, interview experiences, and practice problems that can help you to land your dream job.

Merge sort Program in Java

• Java

Java

import java.util.*;
class Main {
   // Function to merge left and right subarrays of arr.
   public static void mergeTwoSortedArray(int[] leftSubArray, int[] rightSubArray, int[] arr, int n, int m) {
       // i is for leftSubArray, j is for rightSubArray, k is for arr
       int i = 0;
       int j = 0;
       int k = 0;
       while (i < n && j < m) {
           if (leftSubArray[i] <= rightSubArray[j]) {
               arr[k] = leftSubArray[i];
               i++;
           } else {
               arr[k] = rightSubArray[j];
               j++;
           }
           k++;
       }
       // copy remaining elements of leftSubArray[]
       while (i < n) {
           arr[k] = leftSubArray[i];
           i++;
           k++;
       }
       // copy remaining elements of rightSubArray
       while (j < m) {
           arr[k] = rightSubArray[j];
           j++;
           k++;
       }
   }
   public static void mergeSort(int[] arr, int size) {
       // this is a special case - it means we don't have an array to sort. Mind that the array size can never be less than 0
       if (size == 0) {
           return;
       }
       // if only one element is present in arr then we don't need to divide array further as one element is sorted in itself.
       if (size == 1) {
           return;
       }
       // create leftSubArray and rightSubArray - and copy the elements as it is from arr.
       int n = size / 2;
       int m = size - n;
       int[] leftSubArray = new int[n];
       int[] rightSubArray = new int[m];
       // pointer for arr
       int k = 0;
       for (int i = 0; i < n; i++) {
           leftSubArray[i] = arr[k];
           k++;
       }
       for (int j = 0; j < m; j++) {
           rightSubArray[j] = arr[k];
           k++;
       }
       // call mergeSort on left subarray
       mergeSort(leftSubArray, n);
       // call mergeSort on right subarray
       mergeSort(rightSubArray, m);
       // merging the two sorted subarrays back to the original one
       mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m);
       return;
   }
   public static void main(String[] args) {
       int[] arr = {14, 17, 22, 4, 1, 5};
       int n = arr.length;
       mergeSort(arr, n);
       System.out.print("Sorted array: ");
       for (int i = 0; i < n; i++) {
           System.out.print(arr[i] + " ");
       }
   }
}

You can also try this code with Online Java Compiler

Run Code

Output

Sorted array: 1 4 5 14 17 22

Merge sort in Python

• Python

Python

def mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m):
   i = 0
   j = 0
   k = 0
   while i < n and j < m:
       if leftSubArray[i] <= rightSubArray[j]:
           arr[k] = leftSubArray[i]
           i += 1
       else:
           arr[k] = rightSubArray[j]
           j += 1
       k += 1
   while i < n:
       arr[k] = leftSubArray[i]
       i += 1
       k += 1
   while j < m:
       arr[k] = rightSubArray[j]
       j += 1
       k += 1
def mergeSort(arr, size):
   if size == 0:
       return
   if size == 1:
       return
   n = size // 2
   m = size - n
   leftSubArray = [0] * n
   rightSubArray = [0] * m
   k = 0
   for i in range(n):
       leftSubArray[i] = arr[k]
       k += 1
   for j in range(m):
       rightSubArray[j] = arr[k]
       k += 1
   mergeSort(leftSubArray, n)
   mergeSort(rightSubArray, m)
   mergeTwoSortedArray(leftSubArray, rightSubArray, arr, n, m)
arr = [14, 17, 22, 4, 1, 5]
n = len(arr)
mergeSort(arr, n)
print("Sorted array:", end=" ")
for i in range(n):
   print(arr[i], end=" ")

You can also try this code with Online Python Compiler

Run Code

Output

Sorted array: 1 4 5 14 17 22

Merge Sort Examples

Given there are two sorted arrays. We have to merge these two sorted arrays. 

Input

Array 1: 1 3 5 7 9 10
Array 2: 2 6 9 12

Output

1 2 3 5 6 7 9 9 10 12

Now let us see its C, C++, Java, and Python code.

Java Code

• Java

Java

public class MergeSortedArrays {
   public static void merge(int[] nums1, int[] nums2, int n, int m) {
       int[] ans = new int[n + m];
       int i = 0, j = 0, k = 0;
       while (i < n && j < m) {
           if (nums1[i] < nums2[j]) {
               ans[k++] = nums1[i++];
           } else {
               ans[k++] = nums2[j++];
           }
       }
       while (i < n) {
           ans[k++] = nums1[i++];
       }
       while (j < m) {
           ans[k++] = nums2[j++];
       }
       for (i = 0; i < n + m; i++) {
           System.out.print(ans[i] + " ");
       }
   }
   public static void main(String[] args) {
       int[] nums1 = {1, 3, 5, 7, 9, 10};
       int[] nums2 = {2, 6, 9, 12};
       System.out.println("The resultant array is: ");
       merge(nums1, nums2, nums1.length, nums2.length);
   }
}

You can also try this code with Online Java Compiler

Run Code

C Code

• C

C

#include <stdio.h>
void merge(int nums1[], int nums2[], int n, int m) {
  int ans[n+m];
  int i=0,j=0,k=0;
  while(i<n && j<m) {
      if(nums1[i]<nums2[j])
          ans[k++]=nums1[i++];
      else   
          ans[k++]=nums2[j++];
  }
      
  while(i<n)
      ans[k++]=nums1[i++];
      
  while(j<m)
      ans[k++]=nums2[j++];
  
  for(int i=0;i<n+m;i++)
      printf("%d ", ans[i]);
}
int main() {
  int nums1[]={1,3,5,7,9,10};
  int nums2[]={2,6,9,12};
  printf("The resultant array is: \n");
  merge(nums1,nums2,sizeof(nums1)/sizeof(nums1[0]),sizeof(nums2)/sizeof(nums2[0]));
  return 0;   
}

You can also try this code with Online C Compiler

Run Code

C++ Code

• C++

C++

#include <iostream>
using namespace std;
void merge(int nums1[], int nums2[], int n, int m){
   int ans[n+m];
   int i=0,j=0,k=0;
   while(i<n && j<m){
       if(nums1[i]<nums2[j]) //if element at ith position of nums1 is less than element at jth position of
       // nums2, then put the ith element in the ans array.
           ans[k++]=nums1[i++];
       else   
           ans[k++]=nums2[j++]; // else put the jth element in the ans array.
   }
       
   while(i<n)
       ans[k++]=nums1[i++];
       
   while(j<m)
       ans[k++]=nums2[j++];
   
   for(int i=0;i<n+m;i++)
       cout<<ans[i]<<" ";
}
   
int main () {
   int nums1[]={1,3,5,7,9,10};
   int nums2[]={2,6,9,12};
   cout<<"The resultant array is: "<<endl;
   merge(nums1,nums2,sizeof(nums1)/sizeof(nums1[0]),sizeof(nums2)/sizeof(nums2[0]));
   return 0;
   
}

You can also try this code with Online C++ Compiler

Run Code

Python Code

• Python

Python

def merge(nums1, nums2, n, m):
   ans = [0] * (n + m)
   i, j, k = 0, 0, 0
   while i < n and j < m:
       if nums1[i] < nums2[j]:
           ans[k] = nums1[i]
           i += 1
       else:
           ans[k] = nums2[j]
           j += 1
       k += 1
   while i < n:
       ans[k] = nums1[i]
       i += 1
       k += 1
   while j < m:
       ans[k] = nums2[j]
       j += 1
       k += 1
   print(*ans)
nums1 = [1, 3, 5, 7, 9, 10]
nums2 = [2, 6, 9, 12]
print("The resultant array is:")
merge(nums1, nums2, len(nums1), len(nums2))

You can also try this code with Online Python Compiler

Run Code

Applications of Merge Sort

The applications of Merge Sort are:

1. Sorting Large Datasets: Merge sort is efficient for sorting large datasets due to its divide-and-conquer approach, making it suitable for external sorting algorithms.
2. External Sorting: Merge sort is used in external sorting algorithms where data is too large to fit into main memory and must be sorted using disk-based algorithms.
3. Parallel Processing: Merge sort can be parallelized effectively, making it suitable for distributed computing environments and multi-core processors.
4. Stable Sorting: Merge sort maintains the stability of elements with equal keys, making it suitable for applications where maintaining the original order of equal elements is essential.

Advantages of Merge Sort

The advantages of merge sort are:

• Stable Sorting: Merge sort is a stable sorting algorithm, preserving the order of equal elements in the sorted sequence.
• Efficient for Large Datasets: Merge sort has a time complexity of O(n log n) and performs well on large datasets, making it suitable for sorting large collections of data.
• Parallelizable: Merge sort can be easily parallelized, enabling efficient utilization of multi-core processors and distributed computing environments.
• Predictable Performance: Merge sort exhibits consistent performance characteristics, regardless of the input data, making it a reliable choice for sorting.

Disadvantages of Merge Sort

The disadvantages of merge sort are:

• Space Complexity: Merge sort requires additional space proportional to the size of the input array, which can be a disadvantage in memory-constrained environments.
• Not In-place Sorting: Merge sort is not an in-place sorting algorithm, meaning it requires additional space for temporary arrays during the sorting process.
• Recursive Overhead: Merge sort relies on recursion, which can introduce overhead and lead to stack overflow errors for extremely large datasets.
• Not Suitable for Small Datasets: Merge sort may not be the most efficient choice for sorting small arrays or datasets due to its overhead and space requirements.

Difference between QuickSort and MergeSort

Refer to know about :  Topological sort

Frequently Asked Questions

How do you write a merge sort in pseudocode?

We must first consider which sorting algorithm will work the best for the dataset before writing its pseudocode. Then, we'll create the specific sorting algorithm. We will then write the pseudocode in accordance with the sorting method.

What is merge sort formula?

Merge Sort formula:

• Time Complexity: O(n log n) in the worst and average cases.
• Space Complexity: O(n) due to auxiliary storage.
• Stable and efficient sorting algorithm.

What is the pseudocode of merge function?

Pseudocode for the Merge function in Merge Sort:

Merge(arr, left, mid, right)
  // Merge two sorted subarrays arr[left:mid] and arr[mid+1:right] into a single sorted array

Conclusion

In this article, we discussed the merge sort with all the crucial aspects that are necessary to implement the merge sort. We discussed the merge sort algorithm in detail and implemented the merge sort in C++. We also took a look at the time and space complexity of the merge sort in detail.

Recommended Problems:

• Sort A Stack
• Stack Permutation
• Max Stack