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.
How the Merge Sort algorithm works.
Merge Sort is a divide-and-conquer algorithm that sorts an array of elements by dividing it into two halves, sorting each half, and then merging the sorted halves. The algorithm works as follows:
- Divide the array into two halves:
If the array has more than one element, divide it into two halves. The midpoint is calculated as the sum of the left and right indices divided by 2. - Recursively sort each half:
Call the Merge Sort algorithm recursively on the left and right halves until each sub-array has only one element. - Merge the sorted sub-arrays:
Merge the two sorted sub-arrays into a single sorted array. This is done by comparing the first elements of each sub-array and selecting the smaller one to put into a new array. Continue this process until one of the sub-arrays is empty, then copy the remaining elements from the other sub-array into the new array. - Copy the merged array back into the original array:
Copy the sorted elements from the merged array back into the original array.
The algorithm has a time complexity of O(n log n) in the worst case, making it one of the most efficient sorting algorithms. It is a stable sort, meaning that it preserves the order of equal elements, and it can be used to sort various data structures, including arrays, linked lists, and trees.
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.
The Merge Sort Function / Pseudo Code:
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;
}
This is a C++ code for implementing the Merge Sort algorithm. Here are the step-by-step details:
The program starts by including necessary header files and declaring a function named ‘merge’ and another function named ‘mergeSort’.
- The ‘merge()’ function takes in four arguments: an integer array ‘a’, indices ‘l’, ‘r’, and ‘m’. It first calculates the sizes of two sub-arrays using the values of ‘m’, ‘l’, and ‘r’.
- Two new arrays ‘A’ and ‘B’ are created to store the left and right halves of the original input array ‘a’. These sub-arrays are populated using a loop for each of them.
- A new array ‘C’ is created with size equal to the sum of the sizes of ‘A’ and ‘B’.
- A ‘while’ loop is used to compare elements from both ‘A’ and ‘B’ and merge them into the new ‘C’ array in sorted order.
- If there are still any remaining elements in either ‘A’ or ‘B’, they are copied directly to array ‘C’.
Finally, the sorted elements of array ‘C’ are copied back to array ‘a’ in the range specified by indices ‘l’ and ‘r’. The ‘mergeSort()’ function recursively calls itself, passing updated values of ‘l’, ‘r’, and ‘m’ until the base case (l==r) is reached. In the main() function, an example unsorted integer array ‘a’ is declared. The ‘mergeSort()’ function is called on this input array with initial values of ‘l’ and ‘r’.
After sorting, the sorted array is printed using a ‘for’ loop. The program ends by returning 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;
}
This is a C implementation of the Merge Sort algorithm, which sorts an array of integers in ascending order.
The code defines two functions – merge() and mergeSort().
The merge() function takes four arguments – the array to be sorted, the left index, the right index, and the middle index. It divides the array into two sub-arrays and merges them into a single sorted array. It does this by creating three new arrays – A[], B[], and C[]. A[] and B[] represent the left and right sub-arrays, respectively, while C[] is the merged array. The function then compares the first elements of A[] and B[] and selects the smaller one to put into C[]. This process is repeated until one of the sub-arrays is empty, and then the remaining elements of the other sub-array are copied into C[]. Finally, the sorted elements in C[] are copied back into the original array.
The mergeSort() function takes three arguments – the array to be sorted, the left index, and the right index. It recursively divides the array into two halves, calls itself on each half, and then calls the merge() function to merge the two halves into a single sorted array.
In the main() function, an array of integers is declared and initialized, and mergeSort() is called on the array. The sorted array is then printed to the console using a for loop.
The code has a time complexity of O(n log n) in the worst case, making it one of the most efficient sorting algorithms. It is also a stable sort, meaning that it preserves the order of equal elements.
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)
This is an implementation of the Merge Sort algorithm in Python.
The merge function takes in two sorted arrays A and B and returns a single sorted array C that contains all the elements of A and B in sorted order. It does this by comparing the first elements of A and B, adding the smaller element to C, and repeating until either A or B is empty. Then, it adds any remaining elements of A or B to C.
The mergeSort function recursively divides the input array ar into halves until the size becomes 1. Then, it merges the two halves using the merge function. This process continues until the entire array is sorted.
The input array ar is initialized with some integer values, and then mergeSort(ar) is called to sort the array. The sorted array is then printed to the console.
This code implements an efficient divide-and-conquer algorithm for sorting arrays.
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));
}
}
This is an implementation of the Merge Sort algorithm in Java.
The mergeSort() method sorts an array of integers by recursively dividing it into two halves until each sub-array has only one element. Then, it merges the two sorted sub-arrays to form a larger sorted array.
The merge() method is used to merge two sub-arrays. It takes three parameters – the array, the left and right indices of the sub-array, and the middle index (m) which divides the sub-array into two halves. It creates two temporary arrays A[] and B[] to store the left and right halves of the sub-array, respectively. Then, it merges the two arrays into a single sorted array C[] and copies it back to the original array.
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)
This is an implementation of the merge sort algorithm in JavaScript. Merge sort is a divide-and-conquer algorithm that recursively divides an array into two halves, sorts the two halves separately, and then merges them back together.
The merge function takes in two sorted arrays A and B as input and returns a single sorted array C that contains all the elements from both A and B. It does this by iterating through A and B with two pointers i and j, respectively, comparing the values at each pointer and pushing the smaller value onto C. If one of the arrays has been fully traversed, the remaining elements from the other array are simply pushed onto C.
The mergeSort function is the main sorting function that takes in an array a and applies the merge sort algorithm to it. It recursively splits the array in half until the base case of a single-element array is reached, then merges the two halves back together using the merge function.
Finally, the code initializes an unsorted array a, sorts it using mergeSort, and logs the sorted array to the console.
This Javascript Merge Sort implementation has a time complexity of O(n log n) because the array is divided in half log n times and each division requires merging two subarrays of size n, which takes O(n) time.
