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

Question

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.

Answer 1

In terms of time complexity, there can't be a faster method than sorting. If there was, then you could use it to sort faster: Generate the indices and then use them to reorder the original array to be in sorted order. This reordering would take linear time, so overall you would have a faster sort algorithm, creating a contradiction.

Answer 2

insertion sort is iirc pretty low c so works ok on small lists (its also good for almost sorted lists) however are you sure your list is small enough that a sort with better worst case complexity wouldnt be better? a non-in-place merge or quick sort would seem to fit the bill well (a quick sort may well devolve to another sort for very small lists anyway as an optimization).

ultimately to know which is quicker you will have to profile, big O only tells you how complexity grows as n -> infinity