For APLers: I am only concerned with monadic grade up over vectors.

For non-APLers: Grade up is a function that takes a numeric vector V of size n and returns an integer vector R of equal size. The index of the smallest element of V is placed in R[0], the index of the next smallest element in R[1], ..., the largest element of V in R[n-1]. The value of V must be unchanged.

Grading is obviously related to sorting: R provides the indices into V to access V in sorted order. Grade up must be stable: that is, if two elements of V with indices i, j where i < j are equal, then i, j will appear consecutively in R and in that order. An O(n^2) implementation is easy, but I don't see how to adapt a standard stable O(n log n) sorting implementation for this purpose. An algorithm using only constant space would be desirable.

CodePudding user response：

Adapting any comparison sort algorithm is easy. You need to create the vector of indexes R=0..n first and then sort it using comparator function: V[R[i]] < V[R[j]].

The practical implementation of stable O(n log n) sort is Merge Sort, specifically the Tim Sort hybrid variant.

While Merge Sort can be technically implemented with O(1) extra space, the constant will be very high and thus it's not used in practice.

CodePudding user response：

For this particular task, you can use any in-place sorting algorithm: Fill R with the indexes from 0 to n-1, and then just sort it.

For the sort, instead of comparing two indexes i and j by value, you compare S[i] to S[j]. If they are equal, then break the tie by comparing i and j.

Since no two indexes will compare equal, even an unstable algorithm like Quicksort will produce stable results. Many languages include a default sort that takes a comparison function as input.