Merge sort
A divide-and-conquer sorting algorithm recursively dividing data in half, sorting each half, then merging sorted halves. Merge sort guarantees O(n log n) time complexity regardless of input order. Stable sorting maintains equal element order. Requires O(n) auxiliary space for merging.
Formula
T(n) = 2T(n/2) + O(n)
Real World
When Git merges two branches of code, it uses a merge operation nearly identical to merge sort's combine step, comparing changes line by line to produce a unified result.
Exam Focus
Contrast merge sort's guaranteed O(n log n) with bubble sort's O(n²); examiners reward direct comparison of efficiency.
How well did you know this?