In situations where I need to sort a list of large objects, I normally create an separate "OrderedView" or "Ordering" which holds either two lists [comparable_v

In situations where I need to sort a list of large objects, I normally create an separate "OrderedView" or "Ordering" which holds either two lists [comparable_value] and [index] like you describe, or a single list of [comparable_value, index] (depending on the types and languages the second option will be faster). Then it just provides either an iterator. If you only need the ordering once this saves you from going back and re-ordering the original array. If you need to run through the list multiple times, it probably makes sense to actually go back and re-order the original so that the accesses are linear memory. That is, unless the values are pointers in which the indirection will likely kill the benefit.