CKTIS / C++
std::partial_sort — a sorted prefix of a range
std::partial_sort selects the smallest k elements and places them in a sorted prefix of the range. It modifies the input, while the order of the remaining elements is unspecified.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::partial_sort(first, middle, last);
std::partial_sort(first, middle, last, comp);std::partial_sort, declared in <algorithm>, produces a sorted first k elements without sorting the entire range. For k = middle - first, it places in [first, middle) the elements that would appear first after a full sort. The default order is ascending; the overload with comp uses the supplied ordering. It returns void.
The algorithm rearranges elements in the original range. The order in [middle, last) is unspecified: do not assume that this suffix stays unchanged or becomes sorted. Stability is not guaranteed, so elements equivalent under the comparison need not retain their relative order.
Random-access iterators and valid ranges [first, middle) and [middle, last) are required. Elements must support swapping, move construction, and move assignment. Before forming first + k, ensure 0 <= k <= last - first. The comparator must define a strict weak ordering; do not use <= instead of <.
For N = last - first and k > 1, the comparison count is approximately N * log(k). Use this algorithm when you need a sorted best subset of the data. With middle == last, the whole range becomes sorted. The example prints only the three selected elements, so its output does not depend on the unspecified order of the suffix.
Examples
#include <algorithm>
#include <array>
#include <iostream>
int main() {
std::array<int, 6> values{8, 3, 7, 1, 5, 2};
constexpr int k = 3;
std::partial_sort(values.begin(), values.begin() + k, values.end());
for (int i = 0; i < k; ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
}
Result
1 2 3
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.