Basics Information for Merge Sort Time Complexity
- Merge sort can be implemented in four ways ( Normal Top-down implementation, List Top-down implementation, Bottom-up implementation, List Bottom-up implementation).
- Merge Sort time complexity does not vary with different types of implementation.
- List approach implementation of merge sort is take less coding space than the normal approach implementation.
- Merging arrays of length n and m in the merge sort algorithm can take 5n + 12m + o(m) moves during the sorting process.
- A modern, faster, and less time complexity merge sort is the "Block merge sort".
- Many researchers did many operations to stabilize and reduce the merge sort time complexity. Some of them are Katajainen, Geffert.
- There was another algorithm similar to merge sort was called "SymMerge".
A simple merge sort process for (30 40 20 10 70 50 80 90 0 60)
Time Complexity of Merge Sort
Suppose an array of n size needs to be sorted. Then it will take time for T(n). Here is the implementation of Merge Sort. The merge sort function divides the n's thing into two equal parts and the algorithm continues for sorting.
mid = (left + right) / 2;
MergeSort(a, left, mid, n);
MergeSort(a, mid+1, right, n);
Thus, the algorithm for these two divisions (left and right array) takes 2(n/2).
int leftSize = mid - left + 1, rightSize = right - mid;
Now let us see what is happening in the merge function of the merge sort. There is two left and right side for n/2 numbers. Each time we check the head of these two halves and whichever is less is assigned to the temp (a []) array.
for(i=0;i<leftSize;i++)
leftArray[i] = a[left+i];
for(i=0;i<rightSize;i++)
rightArray[i] = a[mid+1+i];
This work is done for n times. If n is removed then all the numbers will be removed. This is done to see which is the smaller number in the array. Then it takes time to do the whole thing is O(n).
Calculation for the Time Complexity of Merge Sort
T(n) = 2T (n/2) + n
= 2 2T 2 (n/4) (n/2) + n
= 2 [ 2T (n/4) + (n/2) ] + n
= 4T (n/4) + 2n
= 8T (n/8) + 3n
= 2^logn T (n/n) + n log n
= n log n
At last, the time complexity of merge sort is n log n or O (n log n)
Merge Sort performance report in the three notations of complexity.
Worst-case performance: (Big-O) O ( n log n )
Best-case performance: (Omega) Ω ( n )
Average performance: (Theta) Θ ( n log n )
Worst-case space complexity: (Big-O) O ( n )
Read Similar Posts:
3. Insertion Sort Time Complexity