Merge Sort Algorithm
Sorting techniques are the most commonly used Algorithms in Programs. Sorting in programming involves placing elements in a list or an array in a certain order. Efficient sorting is important for optimizing other algorithms(such as search and compression algorithms) that require input data to be in sorted lists.
Sorting algorithms are basically a series of instructions. They take an array/list as input and sort them.
There are many sorting algorithms like Bubble Sort, Insertion Sort, Quick Sort etc. But when it comes to efficiency, Merge sort is one of the Best.
Merge Sort
Merge sort is a divide and conquer based algorithm. In divide and conquer approach we divide the problem to solve it. In Merge sort, we first divide the problem into sub problems. When we cannot divide the sub arrays any further, we compare and combine them together till we get the final sorted array.
Since we will be making sub problems out of main problem, Merge sort can be easily implemented using recursion.
We can divide Merge Sort into 3 steps:
a) Divide: Will take the middle element and split the array in two halves
b) Compare: Will compare the elements of sub array
c) Merge: Will merge the sub arrays.
Working:
Let us take an unsorted array A with 8 elements.
Now, we will find the middle element and divide the array in 2 equal halves. In case of odd number of elements, one side is be bound to have one more element than other side, so do not worry about that. In this case, the split point will be between elements 6 and 8.
Now we will keep on doing the same splitting process recursively until we are down to smallest possible sub arrays of the array.
Now, we will compare the elements of the sub arrays with each other and sort them according to their sorted order.
We will now merge the sub arrays back. We will keep on repeating the same process until we get a single sorted array with the same size as that of the original array.
Now, the array A is sorted.
Pseudo-Code:
Here is a Pseudo code of merge sort. For reference, here are some key words.
arr — — Array
left — — Left side subarray
right — — Right side subarray
mid — — Mid element
MergeSort(arr, left, right):if left > rightreturnmid = (left+right)/2mergeSort(arr, left, mid)mergeSort(arr, mid+1, right)merge(arr, left, mid, right)end
Here, Merge function merges two sub arrays into one.
Time complexity:
Recurrence Relation: T(n) = 2T(n/2) + θ(n)
· In the worst case, we are dividing the problem into further 2 sub problems in every iteration. Hence, for n iterations, this will perform (log n) operations, resulting in
o Complexity: O(nlogn)
· In the best case, that is if the array is already sorted, we can do some modification by checking whether the sub array is already sorted or not.
o Complexity: O(nlogn)
· For the average case,
o Complexity: O(nlogn)
Space Complexity:
· Space Complexity of the Problem is: O(n)
Implementation:
Let us look at a C program implementation of Merge sort:
///////////////////////////////////////////////////////////
#include <stdio.h>
void merge(int arr[], int start, int mid, int end) {
int len1 = mid — start + 1;
int len2 = end — mid;
int leftArr[len1], rightArr[len2];
for (int i = 0; i < len1; i++)
leftArr[i] = arr[start + i];
for (int j = 0; j < len2; j++)
rightArr[j] = arr[mid + 1 + j];
int i, j, k;
i = 0;
j = 0;
k = start;
while (i < len1 && j < len2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < len1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < len2)
{arr[k] = rightArr[j];
j++;
k++;}
}
void mergeSort(int arr[], int start, int end) {
if (start < end) {
int mid = start + (end — start) / 2;
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}}
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf(“%d “, arr[i]);
printf(“\n”);}
int main() {
int arr[] = {4, 7, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
printf(“Original array\n”);
display(arr, size);
mergeSort(arr, 0, size — 1);
printf(“Array is sorted:\n”);
display(arr, size);
return 0 ;}
///////////////////////////////////////////////////////////
Output:
///////////////////////////////////////////////////////////
Original array
4 7 12 10 9 1
Array is sorted
1 4 7 9 10 12
///////////////////////////////////////////////////////////
Conclusion:
The merge sort is a divide and conquer based algorithm which uses recursion and has one of the best time complexity in sorting algorithms. It can be used for external sorting, has same time complexity in all cases and can be used to implement stable sort.
However, Merge sort is not the best sorting algorithm. It is not with the least time complexity or memory consumption. But still, it is an excellent algorithm with easy understanding and implementation.
