Example 1 — Find the maximum by halves
Show the steps and the answer
Divide: split the list into halves, then quarters, down to the pairs [7, 2], [9, 4], [1, 8], [6, 3].
Each piece is the same problem, 'find the largest', on fewer items.
Conquer the pairs: 7, 9, 8 and 6, one comparison each, 4 in all.
A pair is small enough to answer directly with one comparison, the base case.
Combine upward: max(7, 9) = 9 and max(8, 6) = 8 with 2 comparisons, then max(9, 8) = 9 with 1.
The largest value of the whole list must be the larger of the two halves' largest values, so each combine costs one comparison.
Count: 4 + 2 + 1 = 7 comparisons, matching with , which gives .
That equals a plain scan, but the four pair comparisons are independent, so four processors could finish in 3 rounds instead of 7 steps.
Answer: The maximum is 9, found with 7 comparisons in 3 rounds.
Takeaway: Divide, solve the tiny pieces directly, and combine with a cheap step. Here the gain is not fewer comparisons but independent work that can run in parallel.