In some programming scenarios it’s useful to get the sort ordering of an array. For example, suppose an array/vector has values [5.5, 3.5, 1.5, 2.5, 4.5]. If you sort the array you’d get [1.5, 2.5, 3.5, 4.5, 5.5]. But instead of directly sorting, a function that gives the sort ordering would return:

array:  5.5  3.5  1.5  2.5  4.5

order:   2    3    1    4    0

This means, “the value in cell 2 belongs in cell [0] in the sorted array, the value in cell 3 belongs in cell [1]”, and so on to “the value in cell 0 belongs in cell [4].” This may be a bit easier to see if you look at the indices of the returned sort order:

  2   3   1   4   0
 [0] [1] [2] [3] [4]

I coded up a function SortOrder using C#. I used a basic Insertion Sort that had a helper array named ordering. Initially ordering is [0, 1, 2, . .]. Instead of actually sorting the source array, I make a copy of the array. Then while sorting the copy, every time there is a swap on the array, I execute a corresponding swap on the ordering array. When done, the original array has not been changed, and the ordering required to sort the array is returned.

So why would this be useful? Suppose you have two parallel arrays. The first holds five employee IDs and the second array holds the corresponding employee names:

555, 333, 222, 111, 444
Bob, Edd, Abe, Don, Cal

Suppose you want to sort by ID number. You can’t just sort each array separately because the IDs would become unassociated with the name order. But if you get the sort order of the employee IDs, you can apply it to both arrays and get the combined sorted result:

111, 222, 333, 444, 555
Don, Abe, Edd, Cal, Bob

Notice that you need a function that applies a sort order to an array. In my code demo, I wrote such a function and called it Rearranged().

Also notice that a sort order is just another name for a mathematical permutation — the numbers 0 through n-1 rearranged. Therefore the function that applies a sort order to an array is exactly the same as a function that applies a permutation to an array. This is a surprisingly interesting problem by itself and one that I’ll write up sometime.

Five paintings by Russian artist Mstislav Pavlov. His art is sort of equal parts abstraction and impressionism. I admire his work greatly, but I generally prefer art that is either more abstract or more impressionist.