C++ Algorithm Sort: std::sort, stable_sort, partial_sort & nth_element Guide

What are sorting algorithms?

Sorting algorithms in the STL rearrange elements into a given order. C++ provides several sorting variants.

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5};

std::sort(v.begin(), v.end());

std::sort(v.begin(), v.end(), std::greater<>());

Why use them?

• Organize data in a defined order
• Enable binary search on sorted ranges
• Performance from tuned implementations
• Flexibility via custom comparators

Kinds of sorting algorithms:

Algorithm	Time	Stable	Typical use
sort	O(n log n)	No	General-purpose sort
stable_sort	O(n log n) ~ O(n log² n)	Yes	Preserve input order for ties
partial_sort	O(n log k)	No	Top k only
nth_element	O(n) average	No	Median or k-th order statistic

Stability: stable_sort keeps relative order for equal keys; sort does not guarantee it.

sort

#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5};

std::sort(v.begin(), v.end());

std::sort(v.begin(), v.end(),  {
    return a > b;
});

Practical examples

Example 1: Sorting structs

#include <algorithm>
#include <vector>
#include <string>

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

int main() {
    std::vector<Person> people = {
        {"Charlie", 35},
        {"Alice", 25},
        {"Bob", 30}
    };
    
    std::sort(people.begin(), people.end(), 
         {
            return a.age < b.age;
        });
    
    for (const auto& p : people) {
        std::cout << p.name << " (" << p.age << ")" << std::endl;
    }
}

Example 2: stable_sort

#include <algorithm>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 90},
        {"Charlie", 85},
        {"David", 90}
    };
    
    std::stable_sort(students.begin(), students.end(),
         {
            return a.score > b.score;
        });
    
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << std::endl;
    }
}

Example 3: partial_sort

#include <algorithm>

int main() {
    std::vector<int> v = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    
    std::cout << "Top 3: ";
    for (int i = 0; i < 3; ++i) {
        std::cout << v[i] << " ";
    }
}

Example 4: nth_element

#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    
    size_t mid = v.size() / 2;
    std::nth_element(v.begin(), v.begin() + mid, v.end());
    
    std::cout << "Median: " << v[mid] << std::endl;
}

Sorting variants summary

std::sort(v.begin(), v.end());
std::stable_sort(v.begin(), v.end());
std::partial_sort(v.begin(), v.begin() + n, v.end());
std::nth_element(v.begin(), v.begin() + n, v.end());
bool sorted = std::is_sorted(v.begin(), v.end());

Common pitfalls

Pitfall 1: Stability

Use stable_sort when equal keys must keep their original relative order.

Pitfall 2: Comparator

std::sort(v.begin(), v.end(),  {
    return a <= b;
});

std::sort(v.begin(), v.end(),  {
    return a < b;
});

Pitfall 3: Performance characteristics

sort — O(n log n) average; stable_sort — O(n log n) to O(n log² n); partial_sort — O(n log k); nth_element — O(n) average.

Pitfall 4: Iterator ranges

std::sort(v.end(), v.begin()) is undefined — keep first <= last.

Usage patterns

std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater<>());
std::stable_sort(v.begin(), v.end());
std::partial_sort(v.begin(), v.begin() + k, v.end());
std::nth_element(v.begin(), v.begin() + mid, v.end());

Production patterns

Multi-key sort (department then salary), Top-K via partial_sort, and banded sorting (priority then deadline) use the same code patterns as the Korean article; reuse std::sort / stable_sort with lambdas comparing multiple fields.

FAQ

Q1: What is sort?

A: A fast sort with O(n log n) average time; not stable.

Q2: What is stable_sort?

A: A stable sort: equal keys keep their original order.

Q3: What is partial_sort?

A: Sorts only the first k elements; O(n log k).

Q4: How do I write a comparator?

A: It must satisfy strict weak ordering. Use <.

Q5: Performance?

A: See table above; use sort for speed when stability is unnecessary.

Q6: How do I verify sorted order?

A: Use std::is_sorted.

Q7: Custom types?

A: Define operator< or pass a comparison function.

Q8: Further reading?

A: Effective STL (Items 31–34), C++ Primer, cppreference — sort.

One-line summary: C++ STL sorting offers efficient options for full sort, stability, partial sort, and order statistics.

---

Related posts

• C++ Algorithm Partition
• C++ Algorithm Guide
• C++ Algorithm Set
• C++ STL algorithm basics
• C++ Algorithm Copy

Practical tips

Debugging

• Fix compiler warnings first; reproduce with small tests.

Performance

• Profile before micro-optimizing; set measurable targets.

Code review

• Match team style; check edge cases.

---

Production checklist

Before coding

• Right tool for the problem?
• Maintainable by the team?
• Meets performance needs?

While coding

• Warnings cleared?
• Edge cases covered?
• Error handling appropriate?

At review

• Intent clear?
• Tests enough?
• Documented where needed?

---

Keywords

std::sort, stable_sort, partial_sort, nth_element, is_sorted, STL, C++, strict weak ordering, comparator