Merge Sort
Merge Sort is an example of the divide and conquer approach. It divides the array into equal halves and then combines in a sorted manner. In merge sort the unsorted list is divided into N sub-lists, each having one element.
Aptitude
Merge Sort
Execution of Merge sort
Dividing
For an unsorted array and we will make a sorted array by using the merge sort algorithm in this array will be used divide and conquer technique.
First of all the array will be divided into N sub-arrays that is the array divided until each has only one element.
Conquering/Merging
The N sub-Arrays will then be merged one by one. Make sure that at each merging step the subarray becomes sorted (see image below). This part of the algorithm is called a conquering/merging.
The sub-arrays are merged in sorted fashion one by one till the resultant is the size of the actual array.
Code
#include<stdio.h>
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void display(int arr[], int size){
int i;
for(i = 0; i < size; i++){
printf("%d ",arr[i]);
}
printf("\n");
}
void main()
{
int a[10]= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
int i;
int size = sizeof(a)/sizeof(a[0]);
printf("Before Sorting : ");
display(a, size);
mergeSort(a, 0, size-1);
printf("After Sorting : ");
display(a, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// create temp arrays to store left and right subarrays
int L[n1], R[n2];
// Copying data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// here we merge the temp arrays back into arr[l..r]
i = 0; // Starting index of L[i]
j = 0; // Starting index of R[i]
k = left; // Starting index of merged subarray
while (i < n1 && j < n2)
{
// place the smaller item at arr[k] pos
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
#include<iostream>
using namespace std;
void mergeSort(int[],int,int);
void merge(int[],int,int,int);
void printArray(int arr[], int size){
int i;
for(i = 0; i < size; i++){
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int array[]= {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
int i;
int size = sizeof(array)/sizeof(array[0]);
cout<< "Before Sorting : ";
printArray(array, size);
mergeSort(array, 0, size-1);
cout<< "After Sorting : ";
printArray(array, size);
}
void mergeSort(int a[], int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right)/2;
// recursive calls to sort first half and second half subarrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// create temp arrays to store left and right subarrays
int L[n1], R[n2];
// Copying data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// here we merge the temp arrays back into arr[l..r]
i = 0; // Starting index of L[i]
j = 0; // Starting index of R[i]
k = left; // Starting index of merged subarray
while (i < n1 && j < n2)
{
// place the smaller item at arr[k] pos
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
//Java Program for Merge Sort
class Main {
// this function display the array
public static void display(int[] arr, int size)
{
for(int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
// main function of the program
public static void main(String[] args)
{
int[] a = {11, 9, 6, 19, 33, 64, 15, 75, 67, 88};
int size = a.length;
System.out.println("Before Sorting : ");
display(a, size);
mergeSort(a, 0, size - 1);
System.out.print("After Sorting : ");
display(a, size);
}
// this function apply merging and sorting in the array
static void mergeSort(int[] a, int left, int right)
{
int mid;
if(left < right)
{
// can also use mid = left + (right - left) / 2
// this can avoid data type overflow
mid = (left + right) / 2;
// recursive calls to sort first half and second half sub-arrays
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
// after sorting this function merge the array
static void merge(int[] arr, int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// create temp arrays to store left and right sub-arrays
int L[] = new int[n1];
int R[] = new int[n2];
// Copying data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// here we merge the temp arrays back into arr[l..r]
i = 0; // Starting index of L[i]
j = 0; // Starting index of R[i]
k = left; // Starting index of merged sub-array
while (i < n1 && j < n2)
{
// place the smaller item at arr[k] pos
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
Before Sorting :
11 9 6 19 33 64 15 75 67 88
After Sorting :
6 9 11 15 19 33 64 67 75 88
Quick Facts about Merge Sort
- The complexity of the merge sort algorithm is O(NlogN) where N is the number of elements to sort.
- It can be applied to file of any sizes.
- In Merge sort all the elements are divided into two sub-array again and again until one element is left.
- After the completion of the divide and conquer the elements are merged to make a sorted array .
- This sorting is less efficient and it require more space as compare to other sorting,
Pros
- Fast ! Time complexity : O(N Log N)
- Reliable, it gives same time complexity in all cases.
- Tim sort variant of this really powerful (Not important for Placements)
Cons
- Space Complexity sucks !!!
- Space Complexity : O(n), most other algorithm have O(1)
Time Complexity for Linear Search
| Best | Worst | Space Complexity |
| O(n Log n) | O(n Log n) | O(n) |
→
←