We know that Time Complexity of std::sort is O(N·log(N)). and
Time Complexity of std::stable_sort is O(N·log^2(N)).

The std::sort doesn't preserves the relative order of equal elements while std::stable_sort does. But it is little slower. Can't we just write custom comparator to preserve order like this

int N = 1e5;
std::vector<int> A(N, 1);

std::vector<int> order(N);
std::iota(order.begin(), order.end(), 0);

std::sort(order.begin(), order.end(), [&](int i, int j) {
    if (A[i] == A[j]) {
        return i < j;
    }
    return A[i] < A[j];
});

now the std::sort will also preserve relative order of equal elements than why to use std::stable_sort