Consider the array ~a_1, a_2, \dots, a_N~ and consider two indices ~i, j~ with ~i < j~. Let ~x~ be the number of elements in the subarray from ~i~ to ~j~ with value between ~a_i~ and ~a_j~ exclusive. Consider how the number of inversions changes if the elements with indices ~i~ and ~j~ are swapped. It turns out that if ~a_i < a_j~, then the number of inversions increases by ~1 + 2 \cdot u~ and if ~a_i > a_j~, then the number decreases by ~1 + 2 \cdot u~. So ~u~ can be determined by swapping ~i~ and ~j~.

Observe that if ~i=1~ and ~j=N~, then the subarray from ~1~ to ~N~ contains every number from ~1~ to ~N~. So the value ~u+1~ is simply the difference between ~a_i~ and ~a_j~. We will extend this idea. First, set ~i=1, j=N~. This tells us ~a_N~ relative to ~a_1~. Next, set ~i=1, j=N-1~. Though the subarray from ~1~ to ~N-1~ is no longer every number, we know the value of ~a_N~ relative to ~a_1~ and ~a_N~ is the only missing number. So we can determine ~a_{N-1}~ relative to ~a_1~. We continue this with ~j=N-2, N-3, \dots, 2~ to determine every element of the array relative to each other. Using this, each element can be identified. This took ~N-1~ swaps (plus another at the start to get the initial number of inversions). Once the elements are known, it is easy to sort the array in ~N-1~ swaps. This totals to ~2N-1~ which is just barely under the limit.

Time Complexity: ~\mathcal{O}(N^2)~