Merge Sort (in C, C++, Java, and Python)

Q: 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.

Q: 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.

Q: 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

Introduction

Merge sort is the process to divide the array into two sections, sort each half, and then merge the sorted section back together. And this process is repeated until the entire array is sorted.

Sorting in programming refers to placing the elements of a Data Structure in a specific and meaningful manner. Sorting is an essential part of data processing.

It is vital to know how these sorting algorithms work internally. Having in-depth knowledge of sorting algorithms will help you to become a great software developer. Merge sort is one of the most efficient sorting algorithms.

Today in this article, we will discuss the merge sort algorithm with its implementation. But before diving into the concepts of merge sort, let’s understand the basics first.

What is merge sort?

Merge sort is a divide and conquer algorithm. It divides the array repeatedly into smaller subarrays until each subarray contains a single element and merges back these subarrays in such a manner that results in a sorted array.

Now the question is, why does it even work? What is its fundamental working principle of merge sort?

The fundamental working principle of merge sort is that an array of size one is always sorted! Meaning, if we consider that we are having only a single element in the array, then the array is sorted, and while merging back, the idea is to merge two subarrays that are sorted. So at the core, this problem is broken down into merging two sorted arrays into a third one which is a famous and a standard question!

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]

Divide: Split into two sublists: [38, 27, 43] and [3, 9, 82, 10].
Divide: Further split the first sublist into [38] and [27, 43].
Divide: Continue splitting the second sublist into [3, 9] and [82, 10].
Conquer: Merge [38] and [27] into [27, 38].
Conquer: Merge [3] and [9] into [3, 9].
Conquer: Merge [82] and [10] into [10, 82].
Merge: Merge [27, 38] and [43] into [27, 38, 43].
Merge: Merge [3, 9] and [10, 82] into [3, 9, 10, 82].
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 Complexity

Merge Sort is a divide-and-conquer algorithm that recursively splits the array into halves until individual elements are reached and then merges them in a sorted manner. Its overall performance is influenced by the splitting, sorting, and merging steps. The time and space complexities of Merge Sort are as follows:

Time Complexity

Merge Sort has a time complexity of O(n log n) in the best, average, and worst cases, where n is the number of elements in the array.

Dividing the Array: The array is repeatedly divided into two halves until each subarray contains only one element. This division process takes O(log n) time because at each level, the array is halved.
Merging the Subarrays: During the merge step, two sorted subarrays are merged into one sorted array. This merging process takes O(n) time for each level of recursion.

Since there are O(log n) levels of recursion, and at each level we perform O(n) work, the total time complexity is O(n log n).

Example of Time Complexity

Consider an array with n = 8 elements:

First, the array is divided into two halves.
Then, those halves are recursively divided again.
Each time the subarrays are merged, O(n) time is required at each level. So, the overall time complexity is O(n log n).

Space Complexity

The space complexity of Merge Sort is O(n). This is because:

Auxiliary Space: Merge Sort uses additional space for the temporary arrays during the merge step. These temporary arrays store the divided elements as they are being merged.
Recursive Call Stack: While Merge Sort is a recursive algorithm, the depth of the recursive call stack is O(log n). However, the main contributor to space complexity is the O(n) space used for storing the arrays during merging.

Thus, the overall space complexity is O(n) due to the additional space required to store temporary arrays for merging.

Implementation of Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce a final sorted array. It is known for its stable time complexity of O(n log n), making it an efficient algorithm for sorting large datasets.

C
C++
Java
Python

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

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

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

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.

C
C++
Java
Python

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++

#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

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

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

Divide and Conquer Strategy

Divide and Conquer is a powerful algorithmic strategy used to solve complex problems by breaking them down into smaller, more manageable subproblems. The basic idea is to divide the problem into two or more smaller subproblems, conquer each of the subproblems recursively, and then combine the results to solve the original problem.

The Divide and Conquer approach is typically applied in algorithms like Merge Sort, Quick Sort, Binary Search, and many more.

Key Steps of Divide and Conquer:

Divide: Break the problem into smaller subproblems. These subproblems should be smaller instances of the same type of problem.
Conquer: Solve the subproblems by applying the same strategy recursively. If the subproblem is simple enough (i.e., a base case), solve it directly without further dividing.
Combine: Combine the solutions of the subproblems to solve the original problem.

Applications of Merge Sort

The applications of Merge Sort are:

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.
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.
Parallel Processing: Merge sort can be parallelized effectively, making it suitable for distributed computing environments and multi-core processors.
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

Basis	Quick Sort	Merge Sort
Division	The list may not always be divided into equal-sized sublists by quicksort. Depending on how we select the pivot, the partition sizes will vary.	A list is split into two equal-sized sublists using merge sort, which then combines the sublists in the best way possible to create a sorted list.
Sorting Type	Quick sort is in place sorting algorithm.	Merge sort is not in place sorting algorithm.
Stability	Quick sort is an unstable sorting algorithm.	Merge sort is a stable sorting algorithm.
Application	Quick sorting is efficient for sorting small datasets.	Merge sort is efficient in sorting linked lists. It is efficient in sorting both small and large datasets.
Time Complexity	The best-case time complexity is O(nlogn).	The best-case time complexity is O(nlogn).
Space Complexity	The space complexity is O(1).	The space complexity is O(n).

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: