DEV Community

Discussion on: Merge Sort

Collapse
sudharsanansr profile image
Sudharsanan Ravichandran Author

Thanks for sharing your insights, could you please help me with resources if you happen to have any?

Collapse
pentacular profile image
pentacular

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.