Merge Sort (Divide & Conquer)

Merge Sort is a recursive, stable sorting algorithm. It works by splitting the array in half until each piece is 1 element long, and then "Merging" those pieces back together in sorted order. It is the gold standard for predictable O(N Log N) performance.

1. The Stable Advantage

Merge Sort is Stable, meaning it preserves the original order of items with equal keys. If you sort a list of 'Orders' by 'CustomerName' and then by 'Date', Merge Sort ensures that orders for the same customer stay in their original date-based order. This is vital for enterprise reporting.

2. The Memory Cost (Extra Space)

Unlike other sorts, Merge Sort is NOT "In-place." It requires an auxiliary array to perform the merge. It has O(N) Space Complexity. If you are sorting 10GB of data, you need another 10GB of RAM just for the algorithm to work.

4. Interview Mastery

Q: "When is Merge Sort better than Quick Sort?"

Architect Answer: "Merge Sort is superior in two cases: 1) When you need **Stability**, and 2) When you are sorting **Linked Lists**. Because recursion in Merge Sort can be implemented by just swapping pointers in a Linked List, it doesn't require the O(N) extra space that it does for arrays. Many external sorting algorithms (sorting data too big for RAM) also use Merge Sort because it accesses data sequentially, which is perfect for disk I/O."