Introduction

std::partial_sort and std::nth_element are both useful when you do not want to sort an entire range, but they optimize for different end results. The important comparison is not just their complexity formulas, but what postcondition each algorithm guarantees after it finishes.

What partial_sort Guarantees

std::partial_sort(first, middle, last) rearranges the range so that:

• the smallest middle - first elements are moved into [first, middle)
• that prefix is fully sorted
• the remainder is left in unspecified order

Example:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> values {9, 1, 8, 2, 7, 3, 6, 4, 5};
7
8    std::partial_sort(values.begin(), values.begin() + 3, values.end());
9
10    for (int v : values) {
11        std::cout << v << ' ';
12    }
13}

After this runs, the first three elements are the three smallest values in sorted order.

According to cppreference, the complexity is approximately N * log(M) comparisons, where N = last - first and M = middle - first.

What nth_element Guarantees

std::nth_element(first, nth, last) is weaker but cheaper. It rearranges the range so that:

• the element at nth is the same one that would appear there in a fully sorted range
• every element before nth is not greater than the nth element
• every element after nth is not less than the nth element
• neither side is fully sorted

Example:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> values {9, 1, 8, 2, 7, 3, 6, 4, 5};
7
8    std::nth_element(values.begin(), values.begin() + 3, values.end());
9
10    for (int v : values) {
11        std::cout << v << ' ';
12    }
13}

The element at index 3 ends up where it would be in sorted order, but the prefix [first, nth) is only partitioned, not sorted.

Cppreference describes nth_element as O(N) comparisons on average. That average-case linear behavior is why it is a strong choice for selection tasks such as finding the median or top-k cutoff.

The Practical Difference

If you need the smallest k elements in sorted order, partial_sort matches the requirement directly.

If you only need to know which element belongs at position k, or you only need the smallest k elements in arbitrary order, nth_element is usually cheaper.

That is the real tradeoff:

• 'partial_sort does more work but gives you a sorted prefix'
• 'nth_element does less work but gives you only partitioning around one pivot position'

Top-K Example

Suppose you want the ten smallest values from a huge vector.

Use partial_sort if you plan to display those ten values in order:

std::partial_sort(values.begin(), values.begin() + 10, values.end());

Use nth_element if you only need membership in the smallest ten:

std::nth_element(values.begin(), values.begin() + 10, values.end());

After nth_element, the first ten items are the ten smallest, but not necessarily sorted.

If you need them sorted afterward, a common pattern is:

std::nth_element(values.begin(), values.begin() + 10, values.end());
std::sort(values.begin(), values.begin() + 10);

That often gives a good balance: partition in average linear time, then sort only the small prefix.

Choosing by Goal

Choose partial_sort when:

• you want the smallest k values already sorted
• 'k is small relative to N'
• the sorted prefix is the actual result you need

Choose nth_element when:

• you need the median or another order statistic
• you need a cutoff value, not a sorted prefix
• you want to partition the data cheaply

The complexity formulas matter, but the output guarantees matter more. An algorithm that computes the wrong postcondition efficiently is still the wrong algorithm.

Memory and Stability

Both algorithms work in place and do not promise stability. If equal elements must preserve their original order, neither one is the right tool by itself.

That is worth remembering because "partial sort" sounds close to "stable sort only on part of the data," but that is not what it means.

Common Pitfalls

The biggest mistake is expecting nth_element to sort the prefix. It does not. It only partitions around the chosen position.

Another mistake is using partial_sort when you only need one statistic such as the median. That pays for sorted output you are not going to use.

Developers also sometimes quote both algorithms as if they solved the same problem with different constants. They do not. Their guarantees are different.

Finally, if you use nth_element for top-k work and then consume the first k elements as if they are ordered, the bug may not show up immediately because the prefix can look almost sorted by accident on some inputs.

Summary

• 'partial_sort produces a sorted prefix of size k with approximately N * log(k) comparisons.'
• 'nth_element places one element at its final sorted position and partitions around it in average linear time.'
• Use partial_sort when you need the smallest k values already ordered.
• Use nth_element when you need selection or partitioning, not a sorted prefix.
• If needed, nth_element plus sort on the prefix is often a strong top-k strategy.