Sorting and Partitioning sort stable_partition
Sort and partition containers with std::sort and std::stable_partition.
Sorting and Partitioning sort stable_partition is a free C++ Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C++ Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
std::sort
The workhorse sorting algorithm. O(N log N) average. In place. Not guaranteed stable.
#include <algorithm>
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end());
// v is sorted ascendingCustom Comparator
Pass a comparator (lambda or functor) to sort by other criteria.
std::sort(v.begin(), v.end(),
[](int a, int b) { return a > b; }); // descendingSorting Custom Types
Provide a comparator that compares specific members, or define operator< on the type.
struct Person { std::string name; int age; };
std::vector<Person> people;
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) { return a.age < b.age; });std::stable_sort
Same as sort, but preserves the relative order of equal elements. Slightly slower (typically O(N log^2 N) extra memory).
std::partial_sort
Place the smallest k elements first (sorted). The remaining elements are in unspecified order. Faster than full sort when you only need the top-k.
std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// first 3 elements are the smallest, sortedstd::nth_element
Partition so the element at nth position is what it would be in a fully sorted range. Everything before is ≤ the nth; everything after is ≥. O(N) average.
std::nth_element(v.begin(), v.begin() + 2, v.end());
// v[2] is the 3rd smallest elementstd::is_sorted
Check whether a range is already sorted.
if (std::is_sorted(v.begin(), v.end())) {
std::cout << "already sorted";
}std::partition
Reorder a range so that elements satisfying a predicate come first. Returns the iterator to the first failing element. Not stable.
std::vector<int> v = {1, 2, 3, 4, 5};
auto pivot = std::partition(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
// even numbers come first, then oddstd::stable_partition
Like partition, but preserves the relative order within each group.
Sorting by Multiple Keys
Use a comparator that compares the primary key, then the secondary if the primary is equal.
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) {
if (a.age != b.age) return a.age < b.age;
return a.name < b.name;
});Binary Search on Sorted Ranges
Once sorted, use std::lower_bound, std::upper_bound, and std::binary_search for O(log N) lookups.
Quick Check
Which algorithm preserves the relative order of equal elements after sorting?
Recap
Use std::sort for general sorting, std::stable_sort when order of equals matters, std::partial_sort for top-k, std::nth_element for selecting, and std::partition/std::stable_partition for grouping.
Frequently asked questions
Is the “Sorting and Partitioning sort stable_partition” lesson free?
Yes — the full text of “Sorting and Partitioning sort stable_partition” is free to read here on the web, and the C++ Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C++ Academy course, upgrade to CoddyKit PRO.
What will I learn in “Sorting and Partitioning sort stable_partition”?
Sort and partition containers with std::sort and std::stable_partition. You practise C++ Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C++ Academy?
No prior experience is required. C++ Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Sorting and Partitioning sort stable_partition” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C++ Academy lesson?
Yes. Every C++ Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Non-Modifying Algorithms find count all_of
- Modifying transform copy_if replace
- Sorting and Partitioning sort stable_partition
- Numeric Algorithms accumulate reduce transform_reduce