Determining the order of a list of numbers (possibly without sorting)

Posted by Victor Liu on Stack Overflow See other posts from Stack Overflow or by Victor Liu
Published on 2010-05-05T23:07:09Z Indexed on 2010/05/05 23:28 UTC
Read the original article Hit count: 225

I have an array of unique integers (e.g. val[i]), in arbitrary order, and I would like to populate another array (ord[i]) with the the sorted indexes of the integers. In other words, val[ord[i]] is in sorted order for increasing i.

Right now, I just fill in ord with 0, ..., N, then sort it based on the value array, but I am wondering if we can be more efficient about it since ord is not populated to begin with. This is more of a question out of curiousity; I don't really care about the extra overhead from having to prepopulate a list and then sort it (it's small, I use insertion sort). This may be a silly question with an obvious answer, but I couldn't find anything online.

© Stack Overflow or respective owner

Related posts about sorting

Related posts about algorithm