Before I came up with my merge sort solution, I tried another idea: Attach the index to each number, then sort the numbers (with their indexes), then see how much each number moved. Take for example input `[5, 2, 6, 1, 3]`

and sort it so it's `[1, 2, 3, 5, 6]`

.

The 5 moved three steps to the right, and that's because there were three smaller numbers on its right initially. So in the result, write down "3" for the 5. Well, it doesn't quite work, but that's the basic idea.

You can see that it doesn't quite work by checking the 2: It moves zero steps, even though there was a smaller number on its right, namely the 1. But while the 1 did push the 2 one step to the right, the 5 pushed it one step to the left, so that overall the 2 didn't move.

So maybe the index differences of the basic idea can somehow be adjusted by the number of rightmovers? Here are the numbers of rightmovers for each index:

```
index: [0, 1, 2, 3, 4]
before: [5, 2, 6, 1, 3]
after: [1, 2, 3, 5, 6]
rightmover changes: [1, 0, 1, -1, -1]
1 numbers moved right from index 0
1 numbers moved right from index 1
2 numbers moved right from index 2
1 numbers moved right from index 3
0 numbers moved right from index 4
```

That was computed by this code in O(nlogn) for sorting plus O(n) for the rest:

```
nums = [5, 2, 6, 1, 3]
rightmover_changes = [0] * len(nums)
indexed_and_sorted = sorted(enumerate(nums), key=lambda x: x[::-1])
for i, (orig_i, num) in enumerate(indexed_and_sorted):
if orig_i < i:
rightmover_changes[orig_i] += 1
rightmover_changes[i] -= 1
print 'index: ', range(len(nums))
print 'before:', nums
print 'after: ', sorted(nums)
print 'rightmover changes:', rightmover_changes
rightmovers = 0
for i, change in enumerate(rightmover_changes):
rightmovers += change
print '{} numbers moved right from index {}'.format(rightmovers, i)
```

I might try again to make this work, but maybe I won't. For now I just wanted to put this out here.