Walk through std::sort, std::stablesort, std::partialsort, and std::nthelement — when would you pick each?
C++Level: IntermediateSTL Containers & Iterators
Walk through std::sort, std::stable_sort, std::partial_sort, and std::nth_element — when would you pick each?
Hints
- Identify types, object lifetimes and compile-time decisions.
- Separate language guarantees from a particular compiler's behavior.
Answer
Sorting
std::sort
:Source: src/algorithm/sort
std::sort rearranges elements in ascending order by default using an introsort
algorithm (a hybrid of quicksort, heapsort, and insertion sort) that guarantees
O(n log n) worst-case complexity. The algorithm requires random access iterators,
so it works with std::vector, std::array, and std::deque, but not with
std::list (use list.sort() instead). For custom ordering, provide a comparison
function or use std::greater<> for descending order. Note that std::sort is
not stable—equal elements may be reordered relative to their original positions.
#include <algorithm>
#include <vector>
int main() {
std::vector v{3, 1, 4, 1, 5, 9, 2, 6};
std::sort(v.begin(), v.end()); // ascending
std::sort(v.begin(), v.end(), std::greater<>{}); // descending
// custom comparator
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
}
std::stable_sort
:Source: src/algorithm/stable-sort
std::stable_sort preserves the relative order of elements that compare equal,
which is essential when sorting by multiple criteria sequentially. For example,
if you first sort employees by name and then by department, employees within the
same department will remain sorted by name. The algorithm uses merge sort and
guarantees O(n log n) complexity when sufficient memory is available, or
O(n log² n) otherwise. Use std::stable_sort when the original ordering of
equivalent elements carries semantic meaning.
#include <algorithm>
#include <vector>
struct Item {
int priority;
int order;
};
int main() {
std::vector<Item> items{{1, 1}, {2, 2}, {1, 3}, {2, 4}};
// stable_sort preserves original order for equal elements
std::stable_sort(items.begin(), items.end(),
[](auto &a, auto &b) { return a.priority < b.priority; });
// items with same priority keep their original relative order
}
std::partial_sort
:Source: src/algorithm/partial-sort
std::partial_sort sorts only the first N elements of a range, leaving the
remaining elements in an unspecified order. This is significantly more efficient
than a full sort when you only need the top N results—it runs in O(n log k) time
where k is the number of elements to sort, compared to O(n log n) for a full sort.
Common use cases include finding the top 10 scores, the 5 smallest values, or
implementing pagination where only the first page needs to be sorted.
#include <algorithm>
#include <vector>
int main() {
std::vector v{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
// sort only first 3 elements
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// v: {0, 1, 2, ...} first 3 are sorted, rest unspecified
}
std::nth_element
:Source: src/algorithm/nth-element
std::nth_element is a selection algorithm that partially sorts a range so that
the element at the nth position is exactly the element that would be there if the
range were fully sorted. All elements before the nth are less than or equal to it,
and all elements after are greater than or equal. This runs in O(n) average time,
making it ideal for finding medians, percentiles, or partitioning data around a
pivot value without the overhead of a full sort.
#include <algorithm>
#include <vector>
int main() {
std::vector v{5, 6, 4, 3, 2, 6, 7, 9, 3};
// find median (middle element)
auto mid = v.begin() + v.size() / 2;
std::nth_element(v.begin(), mid, v.end());
// *mid is now the median value
}
Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT