Merge Sort
Merge Sort
- Complexity is O(n log n)
- Needs more space to merge - proportional to the size of the array
- Stable Sort
-
* Preserves the order of equal elements - Merge Sort does about 39% lower comparisons, in worst case, compared to Quicksort’s average case
- The algo almost always behaves in the same way; taking relatively the same amount of time, whether sorted or unsorted arrays
Testing Notes
- Started testing the algo with two versions.
-
* First version creates two temporary arrays- First version creates only one temporary array
- The sole difference between them is the one that makes second implementation better
Code
As usual the code is available here:
https://github.com/abhi1010/Algorithms