Merge sort sorts a sequence by dividing it into smaller parts, sorting those parts, and merging the sorted results.

The merge step combines two sorted sequences by repeatedly taking the smaller front element. Merging a total of $n$ elements takes

$$O(n)$$

time.

The recursive structure gives the recurrence

$$T(n)=2T(n/2)+O(n),$$

which leads to

$$T(n)=O(n\log n).$$

Merge sort is naturally stable when ties are taken from the left input first. A typical array implementation uses auxiliary storage for merging, while linked or external-data variants can exploit different representations.

The algorithm is a canonical example of divide and conquer where the expensive work happens in the combine step.