NOTE
Merge Sort
Stable O(n log n) divide-and-conquer sorting by merging sorted halves.
This is a historical learning note and may contain outdated or incomplete understanding.
Merge sort recursively sorts two halves and merges the sorted sequences.
It guarantees O(n log n) comparison time and is naturally stable when equal elements are merged in original order. Array implementations usually need O(n) auxiliary storage, while linked/external variants have different memory behavior.
Its predictable sequential merge access is valuable for external sorting and large-data pipelines.