>>10036967nowadays we assume a lot of things to be true that people who wrote papers on merge sort had to rigorously prove.
one example is the optimal substructure property that we take for granted today.
with the advantage of hindsight, we think a lot of things to be trivial.
As another example, we might think that it would be trivial to come up with quicksort as well, but the original partition scheme devised by Hoare actually had a bias that would destroy the proof of the expected O(lg n) time complexity on randomized lists. This is why nowadays we don't learn quicksort with Hoare's original partitioning technique first
