Merge Sort is an algorithm which was invented by John Van Neumann all the way back in 1945.
So the question arises, “Why Merge Sort?”
Why because, Merge sort offers improvement over Selection, Insertion & Bubble Sort as they lack in performance, which scales with (n2) with an input array of n elements whereas the other have a quadratic running time.
Computational Problem that Merge Sort is meant to solve:-
Input- An array of N numbers in arbitrary order.
Output– Numbers in sorted order.
Merge Sort is a canonical application of Divide & Conquer paradigm where we simply take the input array, split it in half & we solve the left half and right part recursively finally combining the results to get a sorted array.
Merge Sort Pseudo code:
C = output [length = n]
A = 1st sorted array [n/2]
B = 2nd sorted array [n/2]
i = 1
j = 1
for k = 1 to n //Traversing the arrays and finding the smallest element.
if A(i) < B(j)
C[k] = A[i]
i++
else
B[j] < A[i]
c[k] = B[j]
j++
end
Running Time of Merge sort:
There are two recursive calls and one merging step.
Running time of merge on array of m numbers <= 4m + 2
Here, 4m is the number of total operations. The operations are: Increment k, Checking the if/else condition, C’s assignment, and i/j’s increment , which sums up to 4m.
2m is for initializing i and j which are both initialized to 1.
Since m >= 1, then- Running time <= 4m + 2m <= 6m.
Claim:
For every input array of n numbers, Merge sort produces a sorted output array and uses at most 6nlog2(n)+6n operations.
Proof:
To prove the claim Recursion-tree method is used.(https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html).
The idea of recursion tree method is to write out all the work done by the recursive Merge sort algorithm in a tree with the children of a given node corresponding to the recursive calls made by that node.
The point of this tree structure is that it will facilitate an interesting way to count the overall work done by the algorithm.
Merge Sort Analysis:
The number of levels a recursion tree has as a function of n, length of the input array is log2(n) – because each time the array gets divided into half, log2(n) is essentially dividing the number n by 2 until it reaches 1.
Pattern in Merge Sort:
At each level, j = 0, 1, 2, 3 … how many number of sub problems are there and what is the size of each sub problem?
Number of sub problems – 2^j
Size of each sub problem – n/(2^j)
Total number of operations at level j <= 2^j * (n/(2^j))
Since merge sort running time is at most 6m,
Total number of operations at level j <= 2^j * 6(n/(2^j)) <= 6n.
This result is independent of j!
Therefore,
Total number of operations <= Total number of operations at level j * number levels <= 6n(log2(n) + 1).
Author: Gautam Chauhan
1CR15IS029
BLOG 