Merge Sort

Merge sort divides an array into two halves, sorts each, and merges. It runs in O(n log n) worst case with O(n) extra space. The merge step can count inversions or merge sorted linked lists. Stable sort — relative order of equal elements is preserved.