What is the difference between std::sort and std::stable_sort?

Question

Accepted Answer

**sort** — not stable. **stable_sort** — preserves order of equal elements.

**std::sort:**
- Not stable.
- Usually introsort (quick + heap + insert).
- O(n log n).

```cpp
struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 30}
};

std::sort(people.begin(), people.end(),
    [](const auto& a, const auto& b) {
        return a.age < b.age;
    }
);
// Alice and Charlie (both 30) may swap
```

**std::stable_sort:**
- Stable.
- Merge sort.
- O(n log n).

```cpp
std::stable_sort(people.begin(), people.end(),
    [](const auto& a, const auto& b) {
        return a.age < b.age;
    }
);
// Alice stays before Charlie (both 30)
```

**When to use stable_sort:**
- Multi-level sorting.
- Preserve original order.

C++: What is the difference between std::sort and std::stable_sort?