## What is it? Merge Sort is a classic divide-and-conquer sorting algorithm. It recursively splits the array in half, sorts each half, then merges the two sorted halves back together. ## How it works - **Divide:** split the array into two halves at the midpoint - **Conquer:** recursively sort each half - **Merge:** merge the two sorted halves into a single sorted array by comparing elements front-to-front and placing the smaller one first - Base case: an array of 0 or 1 elements is already sorted ## When to use - When you need a guaranteed O(n log n) sort regardless of input - Sorting linked lists (no random access needed) - External sorting (data too large to fit in RAM) - When stability is required ## Key Points - Stable sort — equal elements maintain relative order - Not in-place — requires O(n) auxiliary space for the merge step - Consistent O(n log n) time in all cases (best, average, worst) - Good for large datasets where predictability matters