Sorting: Return an array with new positions of each element
Question: I need to sort an array whilst also returning an array which contains the
sorted positions of the original elements. (N.B. not an argsort, the indexes
to sort the array)

At present this requires two steps:

  1. An argsort
  2. A scatter operation on a new array i.e. pos[argsort[i]] = i

I feel like I am missing a trick here. Is this a well known algorithm that I
have overlooked that can be achieved in one step?

Step 2 can also be implemented with a search, but I think the scatter is more
efficient.

I have included some example python code to illustrate the problem.

    
    
    import numpy as np
    
    l = [0,-8,1,10,13,2]
    
    a = np.argsort(l)
    # returns [1 0 2 5 3 4], the order required to sort l
    
    # init new list to zero
    pos = [0 for x in range(0,len(l))]
    
    # scatter http://en.wikipedia.org/wiki/Gather-scatter_(vector_addressing)
    for i in range(0,len(l)):
            pos[a[i]] = i
    
    print pos
    # prints [1, 0, 2, 4, 5, 3], i.e. each original indexes new position in the sorted array
    

Searching for references to this problem has left me frustrated and maybe that
I am missing the correct terminology for this type of operation.

Any help or guidance would be much appreciated.


Answer: Here's a simple implementation, although it's not "in-place" in any meaningful
sense. I'm not sure what you mean by "in-place", since the output is an
np.array of type int and the input could contain doubles.

    
    
    import numpy as np
    
    l = np.array([0,-8,1,10,13,2])
    
    def myargsort(numbers):
      tuples = enumerate(numbers) # returns iterable of index,value
      return np.array([idx for idx,val in sorted(tuples,key = lambda pair: pair[1])])
    
    print(l)
    print(myargsort(l))
    print(np.argsort(l))
    

