Merge Sort splits an array into smaller halves, sorts each half recursively, and merges the results back together. It is one of the clearest examples of divide and conquer in algorithm design.
Why The Runtime Is O(N log N)
Each level of recursion touches every element during the merge step, which costs linear time. The number of levels is logarithmic because the array keeps getting cut in half. Multiply those together and you get O(N log N).
Space Complexity Tradeoff
Merge Sort is fast and stable, but it typically needs extra space to hold intermediate arrays during merging. That makes it different from in-place strategies such as Quick Sort, where memory usage and runtime trade off differently.
Where It Works Well
Merge Sort is a strong choice when predictable performance matters and stable ordering is useful. It also transfers well to linked lists and external sorting scenarios where data does not fit neatly into memory.