Wikipedia provides a reasonable overview of both top-down and bottom-up, and talks about natural merge sorts, and exploiting accidental in-order runs.
I don't see any errors here so it's probably reasonably solid for a wikipedia article.
(Although I haven't gone over it with a fine comb, so I may have missed something)
The critical insight for merge sort is that all sequences of length <= 1 are correctly sorted.
It is also worth noting that the algorithm presented here is a 'top-down merge sort'.
There is also a 'bottom-up merge sort'.
In the bottom up case you skip the sub-division step and just extract two lists of length one from the input, merge, and repeat.
The top-down approach does more work to allow an in-place sort.
The bottom-up approach does less work, but requires more temporary space.
There are also other variations on merge sort.
Merge sort is one of the basic families of sort algorithm and well worth understanding.
Thanks for sharing your insights, could you please help me with resources if you happen to have any?
Wikipedia provides a reasonable overview of both top-down and bottom-up, and talks about natural merge sorts, and exploiting accidental in-order runs.
I don't see any errors here so it's probably reasonably solid for a wikipedia article.
(Although I haven't gone over it with a fine comb, so I may have missed something)
en.wikipedia.org/wiki/Merge_sort#A...
Prinston gives a nice analysis of both top and bottom, and compares with quicksort.
cs.princeton.edu/courses/archive/s...
Quicksort is quite similar to top-down merge sort, so it's useful to understand the differences.