Merge Sort: The Big Picture!
- Explain and trace the merge sort algorithm on a particular data sequence.
The merge sort applies the divide-and-conquer strategy to sort a sequence:
-
Divide the sequence into subsequences of singletons. (A singleton sequence consists of one element, and it is considered to be already sorted.)
-
Successively merge the subsequences pairwise until a single sequence is reformed. Each merge preserves order, so each merged subsequence (and the final merged sequence) are sorted.
Demo
Resources
- Wikipedia's entry on Merge sort.
- HackerEarth's Merge Sort Tutorial with visualizer and coding questions.
- InterviewBit's Merge Sort Tutorial with pictorial examples and a video explanation.
- Toptal's page on Merge Sort with animation, code, analysis, and discussion.
- xSortLab demo on Merge Sort (Along other sorts).