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.

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

Divide the array into two halves: `[1, 5]` and `[3, 2, 4, 0]`

Recursively sort each half

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; }

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

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_{2}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_{2}n).

The time complexity of Merge Sort in worst, average, and best case is Î¸(n*log_{2}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_{2}n function calls waiting in the stack which yields an extra space complexity of O(log_{2}n). So total space complexity becomes O(n+log_{2}n) as n is greater than log_{2}n, we ignore the log_{2}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_{2}n function calls waiting in the stack memory and hence leads to O(log_{2}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

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

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

#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; }

#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

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.

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.