Merge Sort Tracing in AP CSA: How to Trace Without Writing Code

Merge sort appears on the 2026 AP CSA exam as a trace-only topic. You will NOT be asked to write the algorithm, but you need to show how the array splits apart and merges back together. This page teaches the exact tracing technique the exam expects.

🎲 The Big Picture

Merge sort works in two phases:

1. Divide: Keep splitting the array in half until each piece has one element
2. Merge: Combine pairs of sorted pieces back together, maintaining order

✂ Step 1: The Divide Phase

Start with {38, 27, 43, 3, 9, 82, 10}. Split at mid = (0 + 6) / 2 = 3:

             [38, 27, 43, 3, 9, 82, 10]
                    /           \
          [38, 27, 43, 3]    [9, 82, 10]
            /        \         /      \
        [38, 27]  [43, 3]  [9, 82]  [10]
         /   \     /   \    /   \
       [38] [27] [43]  [3] [9] [82]  [10]

Each single element is already “sorted” — that is the base case.

🔄 Step 2: The Merge Phase

Now merge pairs back together. To merge two sorted lists, compare their front elements and take the smaller one:

Merge [38] and [27]:

Compare 38 vs 27. Take 27 first, then 38. Result: [27, 38]

Merge [43] and [3]:

Compare 43 vs 3. Take 3 first, then 43. Result: [3, 43]

Merge [9] and [82]:

Compare 9 vs 82. Take 9 first, then 82. Result: [9, 82]

Merge [27, 38] and [3, 43]:

Merge [9, 82] and [10]:

9 vs 10: take 9. 82 vs 10: take 10. Take 82. Result: [9, 10, 82]

Final Merge [3, 27, 38, 43] and [9, 10, 82]:

📈 Full Trace Tree

DIVIDE (top down):
       [38, 27, 43, 3, 9, 82, 10]
          /                  \
   [38, 27, 43, 3]      [9, 82, 10]
     /        \           /      \
  [38,27]  [43,3]     [9,82]    [10]
  /   \    /   \      /   \
[38] [27] [43] [3]  [9]  [82]

MERGE (bottom up):
[27,38] [3,43]      [9,82]  [10]
    \    /              \    /
 [3,27,38,43]        [9,10,82]
        \               /
   [3, 9, 10, 27, 38, 43, 82]

❌ Common Pitfalls

✏ Practice Questions

❓ Frequently Asked Questions