Merge sort is one of the popular sorting algorithms. The time complexity of this algorithm is O(nlogn).
This algorithm is based on divide and conquer.
Divide and conquer
In the divide-and-conquer approach, a problem is divided into smaller subproblems. We solve smaller subproblems individually and then merge them for the main problem. Again in smaller subproblems, it is divided into another smaller subproblem. We divide until we reach the base case.
Divide and conquer strategy for merge sort
Suppose we have an array A, We are going to sort this array.
Suppose we are going to sort from index l to index r. A[l…r].
First, we divide this array. We take an index between l and r. Suppose this index is m.
Now we will sort subarray A[l..m] and A[m+1…r] individually.
Then we will combine these two sorted subarrays A[l…m] and A[m+1 … r] to create a sorted array A[l … r].
We can choose any index m between l to r. But the best way to choose is that m is the median of the range l to r. This will divide the array in almost half size. This will lead us to a good time complexity which is O(nlogn).
void mergeSort(int a[], int l, int r){
if(l==r) return;
int m=(l+r)/2;
mergeSort(a, l, m);
mergeSort(a,m+1, r);
merge(a, l, r, m);
return;
}
Here we will divide our array until l and r are not the same.
Now, we just need a merge function.
Merge in merge sort algorithm
Suppose we have two sorted arrays A with size n1 and B with size n2. We want to make a sorted array C from these two arrays with length n1+n2.
First, we will take three-pointers i, j, k.
i will maintain the current index of A, j will maintain the current index of B and k will maintain the current index of C.
While i is less than n1 and j is less than n2, we will compare if the ith index of A is smaller than the jth index of B, then we will assign the ith index of A to the kth index of C and then increase both i and k. Otherwise, we will assign the jth index of B to the kth index of C and then increase both j and k.
If one of the arrays of A and B becomes empty, we will append the remaining elements of another array to our resulting array C.
In our above code, we call the merge function with parameter original array a, left index l, right index r, and middle index m respectively.
In our code, we will create an array A=a[l..m] and B=a[m+1 … r].
Then we will merge those arrays and make an array C.
We will again assign a[l…r]=C.
void merge(int a[], int l, int r, int m)
{
int n1=m-l+1;
int n2=r-m;
int n=n1+n2;
int A[n1], B[n2], C[n];
for(int i=l, j=0;i<=m;i++, j++)
{
A[j]=a[i];
}
for(int i=m+1,j=0;i<=r;i++,j++)
{
B[j]=a[i];
}
int i=0, j=0, k=0;
while(i<n1 and j<n2)
{
if(A[i]<=B[j])
{
C[k]=A[i];
i++, k++;
}
else
{
C[k]=B[j];
k++, j++;
}
}
while(i<n1)
{
C[k]=A[i];
k++, i++;
}
while(j<n2)
{
C[k]=B[j];
k++, j++;
}
for(int i=0, j=l;j<=r;j++,i++)
{
a[j]=C[i];
}
return;
}
Merge sort using c++
#include <iostream>
using namespace std;
void merge(int a[], int l, int r, int m)
{
int n1=m-l+1;
int n2=r-m;
int n=n1+n2;
int A[n1], B[n2], C[n];
for(int i=l, j=0;i<=m;i++, j++)
{
A[j]=a[i];
}
for(int i=m+1,j=0;i<=r;i++,j++)
{
B[j]=a[i];
}
int i=0, j=0, k=0;
while(i<n1 and j<n2)
{
if(A[i]<=B[j])
{
C[k]=A[i];
i++, k++;
}
else
{
C[k]=B[j];
k++, j++;
}
}
while(i<n1)
{
C[k]=A[i];
k++, i++;
}
while(j<n2)
{
C[k]=B[j];
k++, j++;
}
for(int i=0, j=l;j<=r;j++,i++)
{
a[j]=C[i];
}
return;
}
void mergeSort(int a[], int l, int r){
if(l==r) return;
int m=(l+r)/2;
mergeSort(a, l, m);
mergeSort(a,m+1, r);
merge(a, l, r, m);
}
int main() {
int a[]={10, 123, 3, 134, 6, 3, 6, 13, 57, 234, 6};
mergeSort(a, 0, 10);
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Merge sort using C
#include<stdio.h>
void merge(int a[], int l, int r, int m)
{
int n1=m-l+1;
int n2=r-m;
int n=n1+n2;
int A[n1], B[n2], C[n];
for(int i=l, j=0;i<=m;i++, j++)
{
A[j]=a[i];
}
for(int i=m+1,j=0;i<=r;i++,j++)
{
B[j]=a[i];
}
int i=0, j=0, k=0;
while(i<n1 && j<n2)
{
if(A[i]<=B[j])
{
C[k]=A[i];
i++, k++;
}
else
{
C[k]=B[j];
k++, j++;
}
}
while(i<n1)
{
C[k]=A[i];
k++, i++;
}
while(j<n2)
{
C[k]=B[j];
k++, j++;
}
for(int i=0, j=l;j<=r;j++,i++)
{
a[j]=C[i];
}
return;
}
void mergeSort(int a[], int l, int r){
if(l==r) return;
int m=(l+r)/2;
mergeSort(a, l, m);
mergeSort(a,m+1, r);
merge(a, l, r, m);
}
int main() {
int a[]={10, 123, 3, 134, 6, 3, 6, 13, 57, 234, 6};
mergeSort(a, 0, 10);
for(int i=0;i<10;i++)
{
printf("%d ", a[i]);
}
return 0;
}
Merge sort using python
def merge(A, B):
C=[]
i=0
j=0
while i<len(A) and j<len(B):
if A[i]<=B[j]:
C.append(A[i])
i=i+1
else:
C.append(B[j])
j=j+1
while i<len(A):
C.append(A[i])
i=i+1
while j<len(B):
C.append(B[j])
j=j+1
return C
def mergeSort(ar):
sz=len(ar)
if sz==1:
return ar
m=sz//2
leftAr=mergeSort(ar[:m])
rightAr=mergeSort(ar[m:])
ar=merge(leftAr, rightAr)
return ar
ar=[10, 123, 3, 134, 6, 3, 6, 13, 57, 234, 6]
ar=mergeSort(ar)
print(ar)
Merge sort using JAVA
import java.util.*;
class MergeSort {
static void merge(int a[], int l, int r, int m)
{
int n1=m-l+1;
int n2=r-m;
int n=n1+n2;
int A[]=new int[n1];
int B[]=new int[n2];
int C[]=new int[n];
for(int i=l, j=0;i<=m;i++, j++)
{
A[j]=a[i];
}
for(int i=m+1,j=0;i<=r;i++,j++)
{
B[j]=a[i];
}
int i=0, j=0, k=0;
while(i<n1 && j<n2)
{
if(A[i]<=B[j])
{
C[k]=A[i];
i++;
k++;
}
else
{
C[k]=B[j];
k++;
j++;
}
}
while(i<n1)
{
C[k]=A[i];
k++;
i++;
}
while(j<n2)
{
C[k]=B[j];
k++;
j++;
}
for(i=0, j=l;j<=r;j++,i++)
{
a[j]=C[i];
}
return;
}
static void mergeSort(int a[], int l, int r)
{
if(l==r) return;
int m=(l+r)/2;
mergeSort(a, l, m);
mergeSort(a,m+1, r);
merge(a, l, r, m);
}
public static void main(String[] args) {
int arr[]={10, 123, 3, 134, 6, 3, 6, 13, 57, 234, 6};
mergeSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
Merge sort using Javascript
function merge(A, B)
{
let C=[]
let i=0, j=0
while(i<A.length && j<B.length)
{
if(A[i]<=B[j])
{
C.push(A[i])
i++
}
else
{
C.push(B[j])
j++;
}
}
while(i<A.length)
{
C.push(A[i++])
}
while(j<B.length)
{
C.push(B[j++])
}
return C
}
function mergeSort(a)
{
if(a.length==1) return a
let m=Math.floor(a.length/2)
let A=mergeSort(a.slice(0, m))
let B=mergeSort(a.slice(m, a.length))
let C=merge(A, B)
return C
}
let a=[10, 123, 3, 134, 6, 3, 6, 13, 57, 234, 6]
a=mergeSort(a)
console.log(a)