Merge Sort — Elegant Divide-and-Conquer Sorting

The Concept#

Merge Sort is a classic Divide and Conquer algorithm. It works by:

1. Dividing the unsorted list into sublists, each containing one element.
2. Repeatedly merging sublists to produce new sorted sublists until there is only one sublist remaining.

---

Code Implementation#

Below is the standard recursive implementation of Merge Sort:

Complexity Analysis#

• Time Complexity: O(N log N) in all cases (best, worst, average). The tree of recursive splits is log N levels deep, and merging elements at each level takes O(N) operations.
• Space Complexity: O(N) auxiliary space to allocate arrays during merging.

---

Interactive Lab: Merge Sort#

Watch how elements split recursively and merge back together into a sorted array. Use the simulation controls to inspect code variables and execution logs.

---

Key Advantages#

• Stable Sort: Preserves the relative order of equal elements.
• Guaranteed Performance: Does not suffer from worst-case O(N^2) behaviors like Quick Sort.