DSA Lab
Merge sort visualizer
Split the list in half, sort each half the same way, then merge the two sorted halves by repeatedly taking the smaller front item. When you need a guaranteed O(n log n) and a stable sort, and for linked lists or data too big for memory.
Merge sort: its cost, and how to use this tool
Time: best O(n log n), average O(n log n), worst O(n log n). Extra memory: O(n). Stable, not in place.
Sort a ready-made input or your own numbers. The bars are the array; the code beside them (in Python, C, C++ or Java) marks the line that just ran, and every step is explained and worked out below the bars.
Lessons that use it
- Merge sort (Algorithms)Divide and conquer: split the array in half, sort each half recursively, and merge two sorted halves in O(n).
- Divide and conquer and the master theorem (Algorithms)Split a problem into smaller copies of itself, solve them recursively, combine the answers, and work out the running time with the master theorem.