为什么归并排序需将未排序列表对半拆分，而非直接拆为单个元素？

Great question! Let’s break this down clearly—because the way we split and merge directly makes or breaks the efficiency of merge sort.

1. Half Splitting Enables the Efficient Merge That Defines Merge Sort #

The core of merge sort is divide and conquer: splitting a big problem into similarly sized subproblems, solving those, then combining the results.

If you split the entire list into all single elements upfront and merge them one by one (like merging [7] with [10], then merging that result with [18], then with [2], and so on), you’re effectively doing a variant of insertion sort—and your time complexity drops to O(n²). Why? Because each time you add a new element to your sorted list, you have to scan the entire sorted list to find the right spot. That adds up to 1+2+3+...+(n-1) operations, which is O(n²) total.

With half splits, though, we merge two similarly sized sorted sublists at each step. For your example:

• First, we split into [7,10,18] and [2,9,45], then split those into smaller halves until we hit single elements.
• Then we merge pairs of small sorted lists: [7]+[10] → [7,10], [2]+[9] → [2,9], then merge those with their single-element counterparts to get [7,10,18] and [2,9,45].
• Finally, we merge those two 3-element sorted lists into the final sorted array.

This approach ensures that every level of merging takes O(n) total time, and since we split the list in half each time, we only have log₂n levels of recursion. The result is the O(n log n) time complexity that makes merge sort so powerful.

2. Recursive Simplicity & Stability #

Half splitting is naturally suited for recursive implementation. The logic is clean: split the list into left and right, sort each recursively, then merge. This makes the code straightforward to write, read, and debug.

Also, while you could technically keep merge sort stable with a one-by-one merge, that approach loses the efficiency that makes merge sort worth using in the first place. The balanced merge from half splits preserves stability (keeping relative order of equal elements) while maintaining O(n log n) speed.

3. Avoiding Unnecessary Recursion Depth #

If you split off one element at a time instead of halving, your recursion depth becomes n (for your 6-element list, that’s 6 levels of recursion). For large datasets, this can lead to stack overflow errors. With half splits, the recursion depth is log₂n—only 3 levels for your example—making the algorithm far more memory-efficient in practice.

To Sum It Up #

Merge sort’s superpower isn’t just splitting into single elements—it’s merging balanced, sorted sublists. Half splitting is the key to enabling that efficient merge, which is why it’s the standard approach.

内容的提问来源于stack exchange，提问作者Andrew the Programmer