This folder contains a clean and efficient implementation of Merge Sort, a classic divide-and-conquer sorting algorithm. Developed by John von Neumann in 1945, Merge Sort works by recursively dividing the array into halves, sorting each half, and then merging the sorted halves back together.
Key strengths:
- Guaranteed O(n log n) time complexity in all cases
- Stable sorting (preserves order of equal elements)
- Excellent for large datasets and linked lists
- Naturally parallelizable
- If the range holds 0 or 1 elements, it is already sorted — stop
- Split the range at its midpoint
- Recursively sort the left half, then the right half
- Merge the two sorted halves by repeatedly taking the smaller front element
Step 4 is where the work happens: merging two sorted lists of combined length n costs exactly n comparisons at most, and the recursion is log n levels deep.
The merge compares with <= rather than <. That single character is what
makes the sort stable — on a tie, the element from the left half is taken
first, preserving the original order.
| Case | Time Complexity | Notes |
|---|---|---|
| Best Case | O(n log n) | Always divides evenly |
| Average Case | O(n log n) | Consistent performance |
| Worst Case | O(n log n) | No degradation |
| Space Complexity | O(n) | Requires temporary arrays for merging |
- Type: Comparison Sort / Divide-and-Conquer
- Stability: ✅ Stable
- In-place: ❌ No (requires O(n) extra space)
- Adaptive: ❌ Not adaptive (same cost regardless of input order)
merge_sort.py— implementation with commentarymerge_sort.html— interactive animation showing the divide and merge phases, open it in any browser