Lets say i have 10 numbers (unsorted)

29,5,23,4,56,21,66,8,43,9

Once i sort them, their indices are changed.

4,5,8,9,21,23,29,43,56,66

I have an index to an element in the unsorted array. Now i want to know which position the same element is in the sorted array. For example, i have the index 6. In the sorted array, it points to the number 66. In the unsorted array, the same element is at index 9.

Is there a way i can find out the index in the second array, in constant time?

I figured read the element at the given index, then apply a binary search in the sorted array to get a O( log(n) ) worst time complexity.

Generating a hash table would require n*log(n) time as well.

I was just wondering if there was a way to sort the elements and store the locations both in one go, so it would take only `n*log(n)`

time, opposed to `2*n*log(n)`

time if we do sort and generating the hash table.

Or if there is some predefined function/container/library in c++ that can be used to accomplish what im trying to do.