Algorithm of Merge Sort in C, C++, Java with Examples | FACE Prep

In this article, we will be discussing Merge sort in C, C++ and Java. So far we have discussed some of the sorting algorithms like Bubble, Selection and Insertion sort. If you observe, all these algorithms are equally inefficient.

In Bubble and Selection sort, we need to traverse the same array many times. Insertion sort is pretty good if most of the array elements are already sorted. But if not, then the same situation occurs. However, Merge sort will be completely different from those and let us see how.

What is Merge Sort Algorithm?

In Merge sort, the given array is sorted using Divide and Conquer algorithm. This algorithm divides the input array into sub-arrays (untill each subarry contains one element only) and then recursively sorts the sub-arrays. The sorted sub-arrays are then merged back together to form a single sorted array. This is where Merge sort differs from all other sorting algorithms.

A simple visualization of this is shown below.

merge sort in c

Merge Sort Pseudo Code

procedure merge(array, start, mid, end) 
num1 = mid - start + 1
num2 = end - mid

// Copy data to temporary arrays arr1[] and arr2[]
for i = 0 to num1
arr1[i] = arr[start + i]
for j = 0 to num2
arr2[j] = arr[mid + 1 + j]

// Merge the temp arrays back into arr[]
i = 0 // Initial index of first subarray
j = 0 // Initial index of second subarray
k = start // Initial index of merged subarray
while (i < num1 and j < num2)
if (arr1[i] <= arr2[j]) then
arr[k] = arr1[i]
i++
end if
else
arr[k] = arr2[j]
j++
end else
k++
end while

// Copy the remaining elements of arr1[], if there are any
while (i < num1)
arr[k] = arr1[i]
i++
k++
end while

// Copy the remaining elements of arr2[], if there are any
while (j < num2)
arr[k] = arr2[j]
j++
k++
end while
end procedure

procedure divide(array, start, end)
if(start < end) then
mid = (start + end) / 2
divide(arr, start, mid)
divide(arr, mid + 1, end)
merge(arr, start, mid, end)
end if
end procedure

Merge Sort in C, C++, Java

Here is the implementation of Merge sort in C, C++ and Java. This implementation is explained with a suitable example in detail below.

#include <stdio.h>

int divide(int arr[], int start, int end)
{
if(start < end)
{
int mid;
mid = (start + end) / 2;
divide(arr, start, mid);
divide(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}

int merge(int arr[], int start, int mid, int end)
{
int i, j, k;
int num1 = mid - start + 1;
int num2 = end - mid;
// create temporary arrays
int arr1[num1], arr2[num2];
// Copy data to temporary arrays arr1[] and arr2[]
for (i = 0; i < num1; i++)
arr1[i] = arr[start + i];
for (j = 0; j < num2; j++)
arr2[j] = arr[mid + 1 + j];

// Merge the temp arrays back into arr[]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = start; // Initial index of merged subarray
while (i < num1 && j < num2)
{
if (arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
}
else
{
arr[k] = arr2[j];
j++;
}
k++;
}

// Copy the remaining elements of arr1[], if there are any
while (i < num1)
{
arr[k] = arr1[i];
i++;
k++;
}
// Copy the remaining elements of arr2[], if there are any
while (j < num2)
{
arr[k] = arr2[j];
j++;
k++;
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}

int main()
{
int n, i;
scanf("%d", &n);
int arr[n];
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
divide(arr, 0, n - 1);
print(arr, n);
}
#include <iostream>
using namespace std;
int merge(int arr[], int start, int mid, int end)
{
int i, j, k;
int num1 = mid - start + 1;
int num2 = end - mid;
// create temporary arrays
int arr1[num1], arr2[num2];
// Copy data to temporary arrays arr1[] and arr2[]
for (i = 0; i < num1; i++)
arr1[i] = arr[start + i];
for (j = 0; j < num2; j++)
arr2[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr[]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = start; // Initial index of merged subarray
while (i < num1 && j < num2)
{
if (arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
}
else
{
arr[k] = arr2[j];
j++;
}
k++;
}

// Copy the remaining elements of arr1[], if there are any

while (i < num1)
{
arr[k] = arr1[i];
i++;
k++;
}

// Copy the remaining elements of arr2[], if there are any

while (j < num2)
{
arr[k] = arr2[j];
j++;
k++;
}
}
int divide(int arr[], int start, int end)
{
if(start < end)
{
int mid;
mid = (start + end) / 2;
divide(arr, start, mid);
divide(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n, i;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
divide(arr, 0, n - 1);
print(arr, n);
}
import java.util.Scanner;

public class Main
{
public static void merge(int arr[], int start, int mid, int end)
{
int i, j, k;
int num1 = mid - start + 1;
int num2 = end - mid;

// create temporary arrays
int arr1[] = new int[num1];
int arr2[] = new int[num2];

// Copy data to temporary arrays arr1[] and arr2[]
for (i = 0; i < num1; i++)
arr1[i] = arr[start + i];
for (j = 0; j < num2; j++)
arr2[j] = arr[mid + 1 + j];

// Merge the temp arrays back into arr[]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = start; // Initial index of merged subarray
while (i < num1 && j < num2)
{
if (arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
}
else
{
arr[k] = arr2[j];
j++;
}
k++;
}

// Copy the remaining elements of arr1[], if there are any

while (i < num1)
{
arr[k] = arr1[i];
i++;
k++;
}

// Copy the remaining elements of arr2[], if there are any
while (j < num2)
{
arr[k] = arr2[j];
j++;
k++;
}
}
public static void divide(int arr[], int start, int end)
{
if(start < end)
{
int mid;
mid = (start + end) / 2;
divide(arr, start, mid);
divide(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
public static void print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int i;
int n = sc.nextInt();
int arr[] = new int[n];
for(i = 0; i < n; i++)
{
arr[i] = sc.nextInt();
}
divide(arr, 0, n - 1);
print(arr, n);
}
}

Example of Merge Sort 

Let us consider an array A={4, 8, 13, 2, 23, 16}. The working of Merge sort for this array of elements is shown below.

merge sort in c

Merge Sort Time Complexity

Here the array consists of 6 elements. So, the number of sub-arrays formed with a single element in it is 6. Then those 6 sub-arrays are merged to 4 sub-arrays. To do this we need 6 append (adding of elements) operations.

Append operation: Comparing the elements and inserting them in sorted order.

Then those 4 sub-arrays are merged to 2 sub-arrays. Again here comes another 6 append operations.

Then those 2 sub-arrays to 1 single sorted array. Another 6 append operations required to do this.

Total 6 + 6+ 6 = 18 append operations. This is the total complexity of the entire merge sort. If the number of array elements keeps increasing, then append operations will also increase. So, in general, total complexity can be (n * log n)

Also See Similar DS Sorting Techniques