Merge Sort
For a general definition of time complexity, see this page.
Merge Sort Time Complexity
The array is divided into ever-tinier components by the Merge Sort algorithm.
When the sub-arrays are combined again, the array is sorted, with the lowest values appearing first.
The array that requires sorting consists of nvariables, and by beginning to examine the quantity of operations required by the method, we may determine the temporal complexity.
The primary functions of Merge Sort are element comparison-based splitting and merging.
To split an array from start until the sub-arrays only consists of one value, Merge Sort does a total of n−1 splits. Just imaging an array with 16 values. It is split one time into sub-arrays of length 8, split again and again, and the size of the sub-arrays reduces to 4, 2 and finally 1. The number of splits for an array of 16 elements is 1+2+4+8=15.
The following graphic illustrates that an array of 16 numbers requires 15 divides.
The quantity of merges is n − as well.1., the same as the total number of splits, as the array must be assembled again after each split. Additionally, a comparison of the values in the sub-arrays is made for every merge in order to sort the combined result.
The worst-case situation that results in the greatest number of comparisons when merging two sub-arrays is when the sub-arrays are of similar size. Just think about combining [2,3,7,8] with [1,4,6,9]. The following comparisons are necessary in this instance:
1.Comparing 1 and 2, result: [1]
2.Comparing 4 and 2, result: [1,2]
3.Comparing 4 and 3, result: [1,2,3]
4.Comparing 4 and 7, result: [1,2,3,4]
5.Comparing 6 and 7, result: [1,2,3,4,6]
6.Comparing 9 and 7, result: [1,2,3,4,6,7]
7.Comparing 9 and 8, result: [1,2,3,4,6,7,8]
The resultant merged array is [1,2,3,4,6,7,8,9], with just the number 9 remaining in one array after the merge. Since the other array is empty, there is no need to compare in order to add the last value. It is evident that seven comparisons are required to combine eight values (four in each of the original sub-arrays). Generally speaking, in the worst situation, n1. In order to obtain a combined array of n principles.
To put it simply, let’s say that we require n comparisons as an alternative to n−1. when combining nprinciples. It’s acceptable to assume this when nis big, and we wish to use Big O notation to compute an upper bound.
So, at each level merging happens, ncomparisons are needed, but how many levels are there? Well, for n=16 we have n=16=24, so 4 levels of merging. For n=32=25 there are 5 levels of merging, and at each level, n comparisons are needed. For n=1024=21010 levels of merging is needed. To find out what power of 2 gives us 1024, we use a base-2 logarithm. The answer is 10. Mathematically it looks like this: log21024=10.
As we can see from the figure above, n comparisons are needed on each level, and there are log2n levels, so there are n⋅log2ncomparison operations in total.
One can compute time complexity by taking the total number of split and merge operations:
===formula====
The number of splitting operations (n−1) can be removed from the Big O calculation above because n⋅log2n will dominate for large n, and because of how we calculate time complexity for algorithms.
The graph below illustrates how executing Merge Sort on an array with n values takes longer.
With Merge Sort, there is less of a disparity between the best and worst case possibilities than with many other sorting algorithms.
Merge Sort Simulation
Run the simulation for different number of values in an array, and see how the number of operations Merge Sort needs on an array of n elements is O(nlogn):
===image===
The number of operations required for “Random,” “Descending,” and “Ascending” is nearly equal if we keep the number of values, n, unchanged.
Because the array is divided and then merged using comparison, whether or not the array has already been sorted, merge sort operates nearly consistently every time.
