Problem context and objectives
Mission briefing
Clockwork game engineer · A tournament scoreboard has jammed
Restore the order before the next round begins: Inversion Counter.
A wrong ordering changes who advances, while a slow repair freezes every active match.
How you win
- 1Recognize when Merge-sort counting matches the clues
- 2Keep this true after every move: each recursive half is sorted and all internal inversions are counted
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: each recursive half is sorted and all internal inversions are counted
Lesson 1 of 3
If the right front beats the left front in sorted halves, it beats every remaining left value. Count that whole block at once.
Your call · Left is [2,4] and the right front is 1. How many inversions are added?