Merge Sort

Overview

Merge sort is a divide-and-conquer algorithm that divides the array into two halves, recursively sorts each half, and then merges the sorted halves back together. It guarantees O(n log n) time complexity and is stable, meaning it preserves the relative order of equal elements.

The Divide Step

The algorithm repeatedly splits the array in half until each subarray contains only one element. A single-element array is trivially sorted. This division creates a binary tree of subproblems that must be solved.

The Conquer Step

After dividing, merge sort recursively sorts both halves. The recursion continues until reaching the base case of single elements, which are already sorted.

The Merge Step

The merge operation combines two sorted arrays into one sorted array by comparing the front elements of both arrays and always taking the smaller one. This process continues until one array is exhausted, then the remaining elements are appended.

Time Complexity

Merge sort has O(n log n) time complexity in all cases—best, average, and worst. The log n comes from the division depth, and n comes from the merge operations at each level. This makes it predictable and reliable.

Space Complexity

Merge sort requires O(n) extra space for the temporary arrays used during merging. This is a trade-off for the guaranteed O(n log n) performance and stability. Some implementations can be optimized to use less space.

Why Merge Sort Matters

Merge sort is excellent when you need guaranteed O(n log n) performance, stability is important, or you're sorting linked lists where it can be implemented with O(1) extra space. It's also a foundation for understanding divide-and-conquer strategies.