Knowledge baseExam Center
ENEnglish
Choose language13

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.

Sources