Merge sort was unique for its time in that the best, worst, and average time complexity are all the same:
Θ(N*log(N)). This means an almost-sorted list will take the same amount of time as a completely out-of-order list. This is acceptable because the worst-case scenario, where a sort could stand to take the most time, is as fast as a sorting algorithm can be.
Some sorts attempt to improve upon the merge sort by first inspecting the input and looking for “runs” that are already pre-sorted. Timsort is one such algorithm that attempts to use pre-sorted data in a list to the sorting algorithm’s advantage. If the data is already sorted, Timsort runs in
Merge sort also requires space. Each separation requires a temporary array, and so a merge sort would require enough space to save the whole of the input a second time. This means the worst-case space complexity of merge sort is
Why does merge sort require so much space? Would it be possible to write an efficient sort that doesn’t require any additional space? Can you think of any trade-offs that would need to be made?