This is more of a general computer science question than Python, but here goes:

Given a list of numbers, I want to create a new list containing ordinals 0 through (len(list) - 1), such that 0 maps to the smallest element in the original list, 1 maps to the second smallest, etc. For example:

[6, 3, 0, 1, 4] → [4, 2, 0, 1, 3]

[0.56, 80, 114, 7, -1, 9e6] → [1, 3, 4, 2, 0, 5]

If two elements in the original list are equal, the order of their mapped ordinals does not matter:

[9, 8, 11, 8, 20] → [2, 0, 3, 1, 4] or [2, 1, 3, 0, 4] are both acceptable.

The solution I have come up with is to:

- Assign an index to each of the elements in the original list.
- Sort the values and their indices, using the values as keys.
- Replace the values in the sorted list with ordinals.
- Sort the list again, this time using the indices as keys.

```
def mapords(L):
d = {k: v for k, v in zip(range(len(L)), L)} # Assign an index to each value.
d = {k: v for k, v in sorted(d.items(), key=lambda i: i[1])} # Sort by value.
d = {k: v for k, v in zip(d.keys(), range(len(L)))} # Replace values with ordinals.
return [v[1] for v in sorted(d.items(), key=lambda i: i[0])] # Sort ordinals by indices.
```

The bottleneck in this algorithm is obviously the two sort calls, which mean the whole thing runs in O(n*log n). Which isn’t terrible, but I *feel* like there should be a solution in linear time. After all, the original list is already sorted, I “just” need to remap it.

Can anyone think of a faster way to do this?