Create a struct that contains two fields: index and value.

Create an array of this structs, where each element (struct) is the original index and value of an element in the array.

Sort the struct using ONLY the value in O(nlogn).

When you are done - iterate the array in the sorted order to get the sorted indices.

use qsort E.g

#include <stdio.h>
#include <stdlib.h>

int *TheArray;

int cmp(const void *a, const void *b){
    int ia = *(int *)a;
    int ib = *(int *)b;
    return (TheArray[ia] > TheArray[ib]) - (TheArray[ia] < TheArray[ib]);
}

int main(void) {
    int a[] = {2,3,4,5,8,2,5,6};
    size_t len = sizeof(a)/sizeof(*a);
    int a_index[len];
    int i;

    for(i = 0; i < len; ++i)
        a_index[i] = i;

    TheArray = a;
    qsort(a_index, len, sizeof(*a_index), cmp);

    for(i = 0; i < len; ++i)
        printf("%d ", a_index[i]);//5 0 1 2 6 3 7 4 : qsort is not a stable.
    printf("\n");

    return 0;
}

Wouldn't this essentially be solveable with an implementation of any sorting algorithm, with the following adjustment:

Where normally you would compare something like: if (a[x] < a[x+1])

You will now be doing: if (a[a_index[x]] < a[a_index[x+1]])

And instead of: swap(a[x], a[x+1])

You'll be doing: swap(a_index[x], a_index[x+1])

(Where a_index is initialized to contain the range of indexes in sequential order initially (0..sizeof(a))

Since essentially a_index is just a lookup-table, where the value for the purpose of sorting is the corresponding value in a. (In practice this is just another level of indirection compared to what we normally do when we sort, as normally we wouldn't compare (x) and (x+1) directly either)

A similar solution can be done without doing in-place sorting as well, as long as you perform all your comparisons against the corresponding values in a, instead of comparing the