Introduction
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. Efficient sorting algorithms are crucial so that we can perform operations that require sorted input optimally.
Whenever we search for something on Amazon or Flipkart, the search result is sorted based on filters like relevance, price, and rating. These companies deal with enormous data sets, so it becomes crucial to use a sorting algorithm that can provide results lightning-fast and provide users a hassle-free experience.
Due to its importance in system design, questions on sorting algorithms are prevalent in technical interviews of companies like Google, Amazon, Microsoft, and Facebook.
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.
Did you know? Merge sort is frequently asked question in Infosys Certification Exam (InfyTQ) 2021
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 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.
#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;
}Output
Sorted array: 1 4 5 14 17 22 Merge sort in C++
Below is the implementation of the merge sort algorithm in 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;
}Output
Sorted array: 1 4 5 14 17 22Time 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 log2n, 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*log2n).
The time complexity of Merge Sort in worst, average, and best case is θ(n*log2n) 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 log2n function calls waiting in the stack which yields an extra space complexity of O(log2n). So total space complexity becomes O(n+log2n) as n is greater than log2n, we ignore the log2n 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 log2n function calls waiting in the stack memory and hence leads to O(log2n) 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
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] + " ");
}
}
}Output
Sorted array: 1 4 5 14 17 22Merge sort in 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=" ")Output
Sorted array: 1 4 5 14 17 22Merge 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 12Output
1 2 3 5 6 7 9 9 10 12Now let us see its C, C++, Java, and Python code.
Java Code
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);
}
}
C Code
#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;
}
C++ Code
#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;
}Python Code
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))
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). |
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 arrayConclusion
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:
