Why Stable Sort?

Revision en1, by maybesomeone, 2022-07-19 17:17:17

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English maybesomeone 2022-07-19 17:17:17 732 Initial revision (published)