Merge sort uses a simple plan: split a list, sort each half, and combine the sorted halves. It is a classic example of divide and conquer.
Divide, solve, combine
Split the input into two parts until each part contains zero or one element. Such a tiny list is already sorted. Then repeatedly merge two sorted lists: compare their first remaining elements, take the smaller one, and continue until both are empty.
Merging two lists containing a total of n elements takes O(n) time. The split creates about log₂(n) levels, so the total running time is O(n log n).
What you trade
Array-based merge sort typically needs O(n) extra space for the temporary merged results. Its predictable running time and stable ordering are valuable: if two records have equal keys, a stable sort keeps them in their original relative order.
Where it fits
Merge sort is useful when predictable performance or stability matters. It also works well for external sorting: if data is too large for memory, sorted chunks can be written to disk and merged in passes.
Other sorting algorithms may use less extra memory or perform faster on typical in-memory data. The right choice depends on input size, stability requirements, available memory, and the guarantees your application needs.