Merge Sort (Stable Split) Explained: Sorting [38, 27, 43, 3, 9, 82, 10]

Imagine you are handed an unordered list of seven integers: nums = [38, 27, 43, 3, 9, 82, 10]. Your goal is to return a fully sorted array. Simple enough, right? But suppose some elements carry hidden secondary data—for instance, two separate records with the value 27 (let's call them $27_A$ and $27_B$) where $27_A$ originally appeared before $27_B$. If your sorting algorithm blindly swaps elements across long distances—like many standard partition-based algorithms do—it might reorder $27_B$ before $27_A$, destroying the original sequence.

Why does that matter? In database sorting, spreadsheet grouping, or multi-key pipelines, losing stability means silent data corruption. You sort by primary key (age), but lose your secondary key sorting (alphabetical name order). We need an approach that splits data down to its atomic units and builds it back up with absolute predictability. That is where merge sort (stable split) shines, guaranteeing that identical keys never cross paths out of turn.

When we look at our locked working array nums = [38, 27, 43, 3, 9, 82, 10], tackling it all at once is chaotic. Instead, the divide-and-conquer model treats the list as a tree of subproblems. We split the array down the middle recursively until every sublist has length 1. A single-element list is trivially sorted. The magic happens on the way back up during the merge step, where two sorted halves are woven together into a single larger sorted list.

To keep our sort stable, we must inspect how elements compare when merging. Imagine our input contains two identical values, say $27_A$ and $27_B$, where $27_A$ originally appeared before $27_B$. As we merge two sorted runs, if both pointers land on a value of 27, our merge routine must pull from the left run first. This strict rule guarantees that identical keys preserve their original relative input order.

Below is the structural skeleton of how this recursive splitting and merging organizes our working array:

[38, 27, 43, 3, 9, 82, 10] <- Original array
/ \
[38, 27, 43, 3] [9, 82, 10] <- Split at midpoint
/ \ / \
[38, 27] [43, 3] [9, 82] [10] <- Further split

By splitting blindly by index rather than value, we guarantee a predictable $O(n\log n)$ execution time regardless of initial input disorder, unlike unstable partition-based sorts.

Now we execute the divide-and-conquer strategy on our running example: nums = [38, 27, 43, 3, 9, 82, 10]. To demonstrate stability, imagine our two 27 values are distinct keys: $27_A$ and $27_B$, where $27_A$ appears first in the input list. As we split and merge, $27_A$ must never be reordered past $27_B$. We follow the complete trace from single-element base cases up to the final combined array.

Given

- Input array: [38, 27_A, 43, 3, 9, 82, 10]
- Goal: Produce [3, 9, 10, 27_A, 27_B, 38, 43, 82] (generalized here without explicit subscripts as [3, 9, 10, 27, 38, 43, 82], preserving $27_A$ before $27_B$).

Steps

- Left branch splits: [38, 27, 43, 3] $\to$ [38, 27] and [43, 3] $\to$ [38], [27], [43], [3]
- Right branch splits: [9, 82, 10] $\to$ [9, 82] and [10] $\to$ [9], [82], [10]

- Merge [38] and [27] $\to$ [27, 38]
- Merge [43] and [3] $\to$ [3, 43]
- Merge [9] and [82] $\to$ [9, 82]
- [10] remains single for now.

- Merge [27, 38] and [3, 43] using two pointers. Comparing 27 and 3, 3 is smaller. Comparing 27 and 43, 27 is smaller. Comparing 38 and 43, 38 is smaller. Result: [3, 27, 38, 43].
- Merge [9, 82] and [10]. Comparing 9 and 10, 9 is smaller. Comparing 82 and 10, 10 is smaller. Result: [9, 10, 82].
4. Final merge: Combine [3, 27, 38, 43] and [9, 10, 82] into the final sorted output.

Result

- Final sorted array: [3, 9, 10, 27, 38, 43, 82]
- Notice how the left-to-right pointer scan during the merge step favors elements from the left sub-array when values are equal, ensuring $27_A$ retains its original precedence over any subsequent identical keys.

Try this: Trace the exact intermediate state when merging [3, 27, 38, 43] and [9, 10, 82] after the first two elements have been pulled into the output buffer.

Now that you have traced the entire divide-and-conquer tree for our locked working array $\text{nums}=[38,27,43,3,9,82,10]$, let us zoom in on the critical moment just before the final combination. Recall from our worked example that the algorithm has finished splitting and sorting the left and right halves into two independent runs. The left run is $[27,38,43]$ and the right run is $[3,9,10,82]$.

Your task is to mentally simulate how the two-pointer merge logic combines these two specific runs into the final sorted array $[3,9,10,27,38,43,82]$. Keep stability in mind: when elements are equal (though none exist between these two specific runs, the comparison rule matters), we prefer the left pointer to maintain original relative order.

Work through the first three pointer comparisons on paper or in your head before checking your mental trace against the target output.

left_run = [27, 38, 43]
right_run = [3, 9, 10, 82]
# Task: Write down the first 4 elements appended to the merged result
# by executing the merge step two-pointer comparisons.

Now that you have mastered how merge sort divides our working array [38, 27, 43, 3, 9, 82, 10] and uses $\le$ during the final merge to preserve equal element ordering, let us test this concept in a new domain. Imagine you are processing a log of user events where each entry has an integer score and a string timestamp, such as [(43, '09:00'), (27, '09:01'), (27, '09:02'), (3, '09:03')]. The elements with score 27 are equal in value, but their arrival timestamps reflect their original sequence.

When you sort these records by score using an unstable sorting algorithm, the relative order of the two 27 entries might invert based on pivot choices or cache swapping. By applying our merge sort mental model, the split and merge phases guarantee that any left-side duplicate is always placed before a right-side duplicate when their keys are identical. This stability is critical in database query engines and multi-column spreadsheets where secondary sort orders must remain undisturbed.

Consider how you would adapt the merge condition in our algorithm if you needed to sort a mixed array of objects instead of primitive integers. The fundamental rule remains: whenever elements compare equal, the element originating from the left subrun must take precedence in the merged buffer.

def stable_merge_objects(left, right):
    # TODO: Merge two lists of tuples (score, label)
    # ensuring equal scores preserve their relative left-to-right order.
    pass