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
The argument that
std::stable_sortis $$$O(Nlog^2 N)$$$ is only partially correct. The truth is, it actually works in $$$O(N log N)$$$, given sufficient memory, and in this situation it is basically identical to Merge Sort. However, when given a low amount of memory,std::stable_sortwill try to use only $$$O(log N)$$$ space complexity, sacrificing time complexity. In this situation, the time complexity is $$$O(N log^2 N)$$$.