Sort an array in increasing order. Merge sort guarantees O of n log n in every case.
DSA Animator › DSA Revision › Sorting Algorithms › Merge Sort
Remember: split, sort halves, merge by taking the smaller front. Guaranteed O of n log n, at the cost of extra memory. The video solves Merge Sort (LeetCode 912, Medium) with the Divide and Conquer pattern from the Sorting Algorithms topic, and you can replay every step in the interactive Merge Sort animation.
Sort an array in increasing order. Merge sort guarantees O of n log n in every case.
For 6, 3, 8, 2, 7, 1, 5, 4, the result is 1 to 8.
Quadratic sorts are fine for small inputs only. Merge sort splits the work in half again and again.
Split the array into two halves. Sort each half recursively, until a part has only one element, which is already sorted. Then merge two sorted halves, by repeatedly taking the smaller front element. Merging two parts costs time proportional to their total length. There are log n levels of halving, so the total is O of n log n.
Split down to single elements, and merge pairs: 3 6, then 2 8. Merge those two pairs into 2, 3, 6, 8. On the right side, merge 1 7 and 4 5. Then merge them into 1, 4, 5, 7. Finally merge 2, 3, 6, 8 with 1, 4, 5, 7, always taking the smaller front value. The result is 1, 2, 3, 4, 5, 6, 7, 8.
In code, merge sort returns when the range has one element. It sorts the left half and the right half. The merge step copies the range, and uses two pointers to write back the smaller front each time. Any leftovers are copied at the end. It's O of n log n time and O of n extra space, and it is stable.
Remember: split, sort halves, merge by taking the smaller front. Guaranteed O of n log n, at the cost of extra memory.