Gamified challenge · Divide and conquer
line[i] is the bib number of the runner in place i. The marshal sorts the line into non-decreasing order using only swaps of two neighbouring runners, and never swaps two runners with equal bibs.
Write inversions(line) that returns the fewest neighbour swaps needed. That is the number of pairs i < j with line[i] > line[j]. Lines can hold over a thousand runners, so aim for O(n log n).
Example: [2, 4, 1, 3, 5] has the out-of-order pairs (2, 1), (4, 1) and (4, 3), so the answer is 3.
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google