Merge Sort

Recursive Decomposition: The algorithm repeatedly bisects the input array into two halves. This logarithmic decomposition ensures that the depth of the recursion tree is exactly $\lceil \log_2 n \rceil$, which is the foundation of its efficient time complexity.

The Sorted Sub-list Assumption: The logic relies on the fact that a list of size one is already sorted. By starting from these atomic units, the algorithm can build larger sorted lists through a systematic comparison process.

Linear Merging: The efficiency of the merge step comes from the fact that two already-sorted lists can be combined into a single sorted list in linear time, $O(n)$, by comparing the heads of each list and moving the smaller element to the result.

Time Complexity: Merge Sort consistently performs at $O(n \log n)$ in the best, average, and worst cases. This is because the number of levels in the recursion tree is $\log n$, and at each level, $n$ comparisons and movements are performed during the merge phase.

Space Complexity: Unlike in-place algorithms like Quick Sort, standard Merge Sort requires $O(n)$ additional space. This auxiliary space is used to store the temporary sub-arrays during the merge process, which can be a significant drawback for memory-constrained environments.

Algorithmic Recurrence: The time complexity can be expressed by the recurrence relation $T(n) = 2T(n/2) + n$. According to the Master Theorem, this solves to $\Theta(n \log n)$.

Linked Lists vs. Arrays: Merge Sort is often preferred for linked lists because it does not require random access to elements. The merge operation can be implemented by simply changing pointers, whereas Quick Sort's partitioning relies heavily on index-based swapping.

External Sorting: Because Merge Sort processes data in sequential chunks, it is the primary algorithm used for External Sorting, where the dataset is too large to fit into RAM and must be sorted using disk storage.

Identify the Pattern: If an exam question asks for a sorting algorithm that guarantees $O(n \log n)$ performance regardless of the input distribution, Merge Sort is the correct answer.

Stability Check: Always mention stability when comparing sorting algorithms. If the problem involves maintaining the order of records with identical keys (e.g., sorting by 'Date' then 'Name'), emphasize that Merge Sort is the reliable choice.

Space Trade-off: Be prepared to discuss the memory overhead. If a question emphasizes 'in-place' sorting or 'minimal memory usage,' Merge Sort is likely not the optimal solution unless specifically adapted.

Recursive Depth: Remember that the depth of the recursion is $\log_2 n$. For an array of 1024 elements, the recursion tree will be 10 levels deep.