Sorting is a technique used to arrange the collection of objects into either ascending order or descending order. There are many sorting algorithms, and merge sort is one of them.
According to Wikipedia, Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
Suppose, we are given with the above array and we want to sort it in the non-decreasing order. Let’s see how merge sort does it for us!
In each step of merge sort,
- We recursively divide the array in two equal parts till it can’t be divided any further, i.e. till the array size is greater than equal to 1. Auxiliary arrays are created of smaller sizes.
- After the divide step, we merge the smaller arrays such the resultant array is in the ascending order.
Merge step in detail
mergeSort = O(nlogn)
merge = O(n)
Let's see how:T(n) = 2T(n/2) + c*n
Here, T(n) is for merge sort for array of size n and 2T(n/2) for two merge sort calls with array of sizes n/2.T(n/2) = 2T(n/4)+ c*n/2
T(n/4) = 2T(n/8)+ c*n/4T(n) = 2(2T(n/4) + c*n/2)+c*n
= 8T(n/8)+3c*nGeneralizing, T(n) = (2^k)T(n/(2^k)) + c*k*nFor, T(1) => n/(2^k) = 1 => n=2^k => k=lognT(n) = nT(1) + nlogn => O(nlogn)
O(nlogn) for all the auxiliary arrays if there is no garbage collection and O(n) for the auxiliary array with garbage collection
Guys I really hope that you find this article valuable! If still you have any queries, you can surely discuss them in the comment section below.
Thanks a lot for devoting your time to this blog.