Introduction
Merge sort is generally considered amongst the fastest sorting algorithms around.
Compared to selection and insertion sort we've looked at in the past, merge is certainly more efficient in most cases, but also harder to implement.
This blog will tell you everything you need to know about merge sort, from its pros and cons and an implementation within C, to a calculation of its time complexity.
So... Why Merge Sort?
It's easy to look past the under-the-hood operations, like system resource usage, and only focus on runtime when dealing with merge sort.
Let's enumerate some of the pros and cons of this sorting method.
Advantages:
Stable sorting algorithm
relative order of elements is preserved once sorted, even those values which are equal
Efficiently sorts arrays of all orders and sizes
number of steps is always a logarithmic function of input size * input size
especially useful for large datasets
Conceptually simple to understand
a larger array is "divided" into smaller ones, and then sorted through merging those smaller arrays
External sorting
when an array is too large to fit into memory, it can be split
Inversion counting
counts the number of steps needed for an array to be sorted
Disadvantages:
NOT in-place sorting algorithm + bad space complexity
requires additional memory to store split and merged arrays
basically, new arrays are created during the sorting process
Merge Sort in C
Before jumping into the full-fledged algorithmic implementation of this "divide-and-conquer" algorithm, let's conceptualize it on a higher level:
The array is split into two halves recursively until all sub-arrays are of length one.
The individual sub-arrays are sorted using recursion.
Once sorted, the sub-arrays are merged together in sorted order, comparing the numbers at the same index value of the two arrays in question.
Sub-arrays are merged together until one, sorted array remains.
We can simulate this algorithm using the list [ 9, 5, 3, 8 ]. Those numbers that are highlighted are being compared to one another.
[9, 5] [3, 8]
[9] [5] [3] [8]
[5, 9] [3, 8]
[3, 5, 8, 9]
Now onto the formal (and slightly lengthy) implementation in C:
Note that the comments (denoted with //) can be helpful in understanding what each part of the program does!
#include <stdio.h>
#include <stdlib.h>
// Merges two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Creates temp arrays
int L[n1], R[n2];
// Adds data from arr[] to L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merges the temp arrays back into arr[l..r]
i = 0;
j = 0;
k = l;
// Compares all values from the left to values on the right
// Adds data back into arr[l..r]
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// The following will happen only of n1 and n2 have different lengths
// Those elements will go at the end as they are implicitly greater
// than the values already in the list
// Copies the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copies the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r)
{
// Calculates the middle of the array
// Checks if the array's length is greater than 0
if (l < r) {
int m = l + (r - l) / 2;
// Splits all arrays into sub-arrays of size 1
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Sorts first and second halves recursively
merge(arr, l, m, r);
}
}
// Prints array
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
// sizeof() returns the total number of bytes
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}Calculating Time Complexity
We can measure this sorting algorithm's efficiency by calculating its time complexity, expressed in terms of the Big-O Notation (worst case scenario) and Big-Omega Notation (best case scenario).
Take a look at my blog on CS50's Week 3 that goes more in-depth into algorithmic efficiency!
For this specific instance, the best case (all elements are pre-sorted) and worst case (all elements are in reverse order) scenarios are the same, as we have to enumerate over every step of the algorithm regardless.
Mathematically...
Let's call T(n) the time complexity of merge sort.
T(n) = T(n/2) + T(n/2) + n, where T(n/2) are the time complexities of the left and right halves of the array, and n is roughly the time complexity needed to merge and sort those halves (see mergeSort() function)
T(n/2) = T(n/4) + T(n/4) + n/2
T(n/4) = T(n/8) + T(n/8) + n/4
T(n) = 2T(n/2) + n, through simplification
T(n) = 2(2T(n/4) + n/2) + n, through substitution
T(n) = 2(2(2(T(n/8) + n/4)+ n/2) + n → 2³ * T(n/2³) + 3n, through substitution
T(1) = 1, as we know that if the array is of size one, the array is "sorted" and only one check is needed (hence one step)
n/2ˣ = 1 → x = log₂(n), finding a value for x at which T(n/2ˣ) = 1
T(n) = 2ˣ * T(n/2ˣ) + xn, rewritten in terms of x
T(n) = n + nlog₂(n), substituting in the value of x
Phew! Now, because the most prominent term is nlog₂(n), we can express this as θ(nlog₂(n)) or simply θ(nlog(n)).
Notice how instead of using Big-O or Big-Omega notations, we used Big-Theta notation to convey that the worst case and best case have the same time complexities.
Final Thoughts
Although merge can seem scary at first, it's definitely a great algorithm to have in your arsenal. Also, for me at least, finding merge sort's unconventional time complexity was definitely a challenge, but also extremely satisfactory and mathematically beautiful.
This was merge sort!
Comments