In this chapter we shall learn about below topics:
4.1 Definition
4.2 Steps for performing Merge Sort
4.3 Understanding Merge Sort with an example
4.4 Implementation of Merge Sort in C
4.5 Output of the program
4.6 Time complexity analysis of Merge Sort
4.1 Definition
Merge sort is based on divide and conquer technique.
4.2 Steps for performing Merge Sort
Divide: Divide the array into half. If the array has n elements, in the first level divide it by n/2. Then take those 2 array again divide it by 2. Go on till you get only single elements.
Conquer: Sort the left part of the array and right part of the array recursively.
Combine: Combine the left part of the array and the right part of the array into single sorted array.
4.3 Understanding Merge Sort with an example
Below is the image for merge sort performed for the array [40, 10, 5, 20, 15, 34, 7, 9]
Divide:
As we have 8 elements, the middle index will be 4. Hence we divide the array into 2 parts. If you observe the code, once we divide the array, we recursively call the left part of the sub array till it becomes sorted and then call the right part of the sub array.
Keeping that in mind we shall trace how the algorithm will work.
First it will divide left part of the array as below:
Then again, we have 4 elements, middle element is 2, again divide the left part of the array as shown below:
Again we have 2 elements divide it as shown below:
As we have completed the left part, we go 1 level up and divide the right part as below:
Now the left and right part has been divided, we combine them into a sorted array as shown below:
Now we split the right part of the sub array as shown:
Again we split the array as below:
Then we merge them as below:
Then we sort and merge whole sub array as below:
Similarly we do the same for right sub array. While performing for the right sub array, we again choose the left part of the right sub array and do the similar operation. The full recursion tree will look like below:
Below I have mentioned the steps on how the dividing and conquer will occur.
Steps to perform merge sort:
To perform merge sort, we need 3 elements:
1. The array to be sorted.
2. Lowest index.
3. Highest index.
We need lowest and highest index to calculate the mid part of the index and divide the array into two parts which later can be merged.
Algorithm MergeSort(array, low, high)
If (low < high)
mid <- (low + high) /2 // To divide the array into left and right array.
MergeSort(array, low, mid) // Sort left array.
MergeSort(array, mid + 1, high) // Sort right array.
MergeSortedArray (a, low, mid, high) // Merge the sorted left and right array4.4 Implementation of Merge Sort in C
#include<stdio.h>
void print_array(int array[], int length)
{
int index = 0;
printf("The sorted array is \n");
for(index = 0 ; index < length ; index++)
{
printf("%d\n",array[index] );
}
}
void merge_sorted_array( int array[], int low, int mid_index, int high)
{
int temp_array [100];
int i = low;
int j = mid_index + 1 ;
int k = low;
while (i <= mid_index && j <= high)
{
if(array[i] < array [j])
{
temp_array [k] = array[i];
i++;
k++;
}
else
{
temp_array [k] = array[j];
j++;
k++;
}
}
//copy the left part of the array to temp_array
while(i <= mid_index)
{
temp_array [k] = array[i];
k++;
i++;
}
//copy the right part of the array to temp_array
while(j <= high)
{
temp_array [k] = array[j];
k++;
j++;
}
//copy the tem_array to original array
for(i =0 ; i <= high; i++)
{
array[i] = temp_array[i];
}
}
void merge_sort (int array[], int low, int high)
{
int mid_index = 0;
if (low < high)
{
mid_index = (low + high) / 2;
merge_sort(array, low, mid_index);
merge_sort(array, mid_index + 1, high);
merge_sorted_array(array, low, mid_index, high);
}
}
int main()
{
int length = 0;
int array[100];
int index = 0;
printf("Enter the length of the array\n");
scanf("%d", &length);
printf("Enter the array elements of length %d\n", length);
for (index = 0; index < length; ++index)
{
scanf("%d", &array[index]);
}
merge_sort(array, 0, length - 1 );
print_array(array, length);
}
4.5 Output of the program:
Enter the length of the array
5
Enter the array elements of length 5
5
4
3
2
1
The sorted array is
1
2
3
4
5
4.6 Time complexity analysis of Merge Sort
Total time taken for merge sort = Time taken to sort left half + Time taken to sort left half +Time taken to merge left and right half.
T(n) = T (n/2) + T (n/2) + n
= 2 T(n/2) + n —-> Equation 1
Now we need to calculate the time taken for T(n/2). Replace n with n/2 in equation 1.
T(n/2) = 2 * T(n/2/2) + n/2
= 2T(n/2^2) + n/2 —–> Equation 2.
Now replace the value of n/2 from equation 2 to equation 1.
T(n) = 2 { 2T(n/2) + n/2) + n
2^2 T(n/2^2) + n + n
=2^2 * T (n/4) + 2n —> Equation 3.
Now we need to find the value for T(n/4). Hence replace n with n/4 in equation 1, we get
T(n/4) = 2 T(n/8) + n/4.
Now replace the value of T(n/4) with the result above.
T(n) = 2^2 { 2T (n/8) + n/4)} + 2n
= 2^3 * T(n/2^3) + n + 2n. [here 4 and n/4 cancels each other giving us “n”].
= 2^3 * T(n/8) + 3n –> Equation 4
Now again we need to calculate the value of T(n/8), by replacing in equation 1, and replacing in equation 4 we get:
=2^4 * T (n/2^4) + 4n
Similarly, for T(n/2^4) we get
= 2^5 * T(n/2^5) + 5n
Hence for ith value, we can write as:
T(n) = 2^i * T (n/2^i) + i*n –> Equation 5
Once we recursively start to get the value of T(n/2^i), it will be reduced to 1.
Hence
n/2^i = 1
n = 2^i -> Equation 6
i = log n -> Equation 7
Now substitute equation 6 and 7 in 5 we get:
T(n) = n*T(1) + log n * n
= n + n log n
O(n log n).