In this tutorial, you will learn about merge sort. Likewise, you will discover working instances of merge sort C, C++, Java, and Python.
Merge sort is perhaps the most prominent divide-and-conquer sorting algorithms in modern time. It tends to be used to sort the values in any traversable data structure such as a list.
Merge Sort is quite possibly the most popular sorting algorithm that depends on the principle of the Divide and Conquers Algorithm.
Here, an issue is divided into various sub-issues. Each sub-issue is solved exclusively. At long last, sub-issues are combined to form the last arrangement.
In this article, you will learn-
Divide and Conquer Strategy
Using the Divide and Conquer procedure, we divide an issue into subproblems. At the point when the solution for each subproblem is prepared, we ‘combine’ the outcomes from the subproblems to tackle the main issue.
Assume we needed to sort an exhibit A. A subproblem is sorted into a sub-segment of this array beginning at index p and finishing at index r denoted as A[p..r].
Divide
On the off chance that q is the midpoint among p and r, we can part the subarray A[p..r] into two arrays A[p..q] and A[q+1, r].
Conquer
In the conquer step, we attempt to sort both the subarrays A[p..q] and A[q+1, r]. In the event that we haven’t yet arrived at the base case, we again partition both these subarrays and attempt to sort them.
Combine
At the point when the conquer step arrives at the base step and we get two sorted subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the outcomes by creating a sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1, r].
The MergeSort Algorithm
The MergeSort work consistently divides the array into equal parts until we arrive at a phase where we attempt to perform MergeSort on a subarray of size 1 for example p == r.
From that point onward, the merge function becomes possibly the most important factor and combines the sorted arrays into larger arrays until the entire array is merged.
MergeSort(A, p, r):
if p > r
return
q = (p+r)/2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
To sort a whole array, we need to call MergeSort(A, 0, length(A)- 1).
As demonstrated in the picture underneath, the merge sort algorithm recursively divides the array into equal parts until we arrive at the base instance of the array with 1 element. From that point onward, the merge picks up the sorted sub-arrays and merges them to bit by bit sort the whole array.
The merge Step of Merge Sort
Each recursive algorithm is dependent on a base case and the ability to combine the outcomes from base cases. Merge sort is the same. The main piece of the merge sort algorithm is, you guessed it, the merge step.
The merge step is the solution for the straightforward issue of merging two sorted lists(arrays) to assemble one enormous arranged list(array).
The algorithm keeps three-pointers, one for every one of the two arrays and one for keeping up the current index of the last sorted array.
Have we reached the end of any of the arrays?
No:
Compare current elements of both arrays
Copy smaller element into sorted array
Move pointer of element containing smaller element
Yes:
Copy all remaining elements of non-empty array
Writing the Code for Merge Algorithm
A noticeable difference between the merging step we described above and the one we use for merge sort is that we just play out the merge function on sequential sub-arrays.
This is the reason we just need the array, the first position, the last index of the first subarray(we can configure the primary file of the second subarray), and the last index of the second subarray.
Our task is to merge two subarrays A[p..q] and A[q+1..r] to make an arranged cluster A[p..r]. So the contributions to the function are A, p, q and r
The merge work fills in as follows:
- Create duplicates of the subarrays L ← A[p..q] and M ← A[q+1..r].
2. Create three pointers I, j and k
a. i keeps up current index of L, beginning at 1
b. j keeps up current index of M, beginning at 1
c. keeps up the current index of A[p..q], beginning at p.
3. Until we arrive at the finish of one or the other L or M, pick the bigger among the elements from L and M and spot them in the correct situation at A[p..q]
4. At the point when we run out of elements in one or the other L or M, get the remaining elements and placed them in A[p..q]
In code, this would resemble:
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
Merge( ) Function Explained Step-By-Step
A lot is occurring in this function, so we should take an example to see how this would function.
As usual, a picture speaks a thousand words.
The array A[0..5] contains two sorted subarrays A[0..3] and A[4..5]. Let us to see how the merge function will merge the two arrays.
void merge(int arr[], int p, int q, int r) {
// Here, p = 0, q = 4, r = 6 (size of array)
Step 1: Create duplicate copies of sub-arrays to be sorted
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;
int L[4], M[2];
for (int i = 0; i < 4; i++)
L[i] = arr[p + i];
// L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]
for (int j = 0; j < 2; j++)
M[j] = arr[q + 1 + j];
// M[0,1,2,3] = A[4,5] = [6,9]
Step 2: Maintain a current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
Step 3: Until we reach the end of either L or M, pick larger among elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i]; i++;
}
else {
arr[k] = M[j];
j++;
}
k++;
}
Step 4: When we run out of elements in either L or M, pick up the remaining elements and put in A[p..r]
// We exited the earlier loop because j < n2 doesn't hold
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// We exited the earlier loop because i < n1 doesn't hold
while (j < n2)
{
arr[k] = M[j];
j++;
k++;
}
}
This progression would have been required if the size of M was greater than L.
Toward the finish of the merge function, the subarray A[p..r] is sorted.
Python, Java and C/C++ Examples
Python
# MergeSort in Python
def mergeSort(array):
if len(array) > 1:
# r is the point where the array is divided into two subarrays
r = len(array)//2
L = array[:r]
M = array[r:]
# Sort the two halves
mergeSort(L)
mergeSort(M)
i = j = k = 0
# Until we reach either end of either L or M, pick larger among
# elements L and M and place them in the correct position at A[p..r]
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1
# When we run out of elements in either L or M,
# pick up the remaining elements and put in A[p..r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1
# Print the array
def printList(array):
for i in range(len(array)):
print(array[i], end=" ")
print()
# Driver program
if __name__ == '__main__':
array = [6, 5, 12, 10, 9, 1]
mergeSort(array)
print("Sorted array is: ")
printList(array)
Java
// Merge sort in Java
class MergeSort {
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1];
int M[] = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver program
public static void main(String args[]) {
int arr[] = { 6, 5, 12, 10, 9, 1 };
MergeSort ob = new MergeSort();
ob.mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array:");
printArray(arr);
}
}
C
// Merge sort in C
#include <stdio.h>
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}
C++
// Merge sort in C++
#include <iostream>
using namespace std;
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
// Maintain current index of sub-arrays and main array
int i, j, k;
i = 0;
j = 0;
k = p;
// Until we reach either end of either L or M, pick larger among
// elements L and M and place them in the correct position at A[p..r]
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
// When we run out of elements in either L or M,
// pick up the remaining elements and put in A[p..r]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
// Divide the array into two subarrays, sort them and merge them
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m is the point where the array is divided into two subarrays
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted subarrays
merge(arr, l, m, r);
}
}
// Print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}
Merge Sort Complexity
Time Complexity
Best Case Complexity: O(n*log n)
Worst Case Complexity: O(n*log n)
Average Case Complexity: O(n*log n)
Space Complexity
The space complexity of merge sort is O(n).
Merge Sort Applications
- Inversion count issue
- Outside sorting
- E-commerce applications
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
