Exercise 2: Hand-Tracing MergeSort on [9, 4, 6, 1] — Possible Solution
====================================================================

THE SPLIT
------------------------------
list = [9, 4, 6, 1], length 4, mid = 2
Left half:  [9, 4]
Right half: [6, 1]

SOLVING THE LEFT HALF: MergeSort([9, 4])
------------------------------
Split again: [9] and [4], both base cases (length 1, already sorted).
Merge([9], [4]):
  compare 9 and 4: 4 is smaller, move it first -> result=[4]
  left is now empty of unmoved elements except 9 remains
  append remaining left elements: result=[4, 9]
Result: [4, 9]

SOLVING THE RIGHT HALF: MergeSort([6, 1])
------------------------------
Split again: [6] and [1], both base cases.
Merge([6], [1]):
  compare 6 and 1: 1 is smaller, move it first -> result=[1]
  append remaining left elements (6): result=[1, 6]
Result: [1, 6]

FINAL COMBINE: Merge([4, 9], [1, 6])
------------------------------
  compare left[0]=4 and right[0]=1: 1 is smaller -> result=[1]
  compare left[0]=4 and right[0]=6: 4 is smaller -> result=[1, 4]
  compare left[0]=9 and right[0]=6: 6 is smaller -> result=[1, 4, 6]
  left still has 9 remaining, right is now empty
  append remaining left elements (9): result=[1, 4, 6, 9]

FINAL SORTED RESULT: [1, 4, 6, 9]

WHY THIS WORKS AS AN ANSWER
------------------------------
The trace follows this chapter's own established tracing style exactly
- splitting down to every base case, merging pairs back up step by
step with each individual comparison shown, and ending with a fully
combined result - rather than skipping directly to a claimed final
answer.