Introduction

std::nth_element is not supposed to fully sort a range. It only guarantees that the element at position nth is the same one that would appear there in a fully sorted sequence, with everything before it not greater and everything after it not smaller. If you see full sorting for ranges of size 32 or less, that is usually an implementation detail of your standard library, not part of the C++ standard contract.

What std::nth_element Guarantees

The algorithm reorders the range so that:

• '*nth is the correct nth element'
• everything before nth is less than or equal to *nth
• everything after nth is greater than or equal to *nth

It does not promise that either side is sorted.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> values{9, 3, 7, 1, 5, 8, 2, 6, 4};
7
8    auto nth = values.begin() + 4;
9    std::nth_element(values.begin(), nth, values.end());
10
11    std::cout << "nth value: " << *nth << "\n";
12    for (int v : values) {
13        std::cout << v << ' ';
14    }
15    std::cout << '\n';
16}

The output is usually partitioned around the fifth-smallest value, but not completely sorted.

Why Small Ranges May End Up Sorted Anyway

Many standard library implementations use hybrid algorithms. For large ranges, nth_element uses a selection-oriented strategy similar to quickselect or introselect. For very small subranges, however, implementations often switch to a simpler algorithm such as insertion sort because:

• the constant factors are lower
• branch behavior is friendlier
• small partitions are cheap to finish with a straightforward sort

If the whole input range is already below that internal cutoff, the implementation may end up fully sorting it even though that is more work than the abstract guarantee requires.

That is why a vector of size 32 might look sorted while a vector of size 33 does not.

This Is Not a Language Rule

The key point is that the threshold is not standardized. The C++ standard specifies observable guarantees and complexity bounds, not the exact algorithm or cutoff value an implementation must use.

So statements like "it sorts vectors smaller than 33 elements" should be read as:

"My current STL implementation appears to sort small ranges, probably because of an internal optimization threshold."

That behavior may differ across:

• libstdc++
• libc++
• MSVC's STL
• compiler versions
• build modes

You should not write code that depends on the full-sort side effect.

A Small Demonstration

Here is a quick test program that checks whether the resulting range happens to be fully sorted:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5bool is_sorted_after_nth(std::vector<int> values) {
6    auto nth = values.begin() + values.size() / 2;
7    std::nth_element(values.begin(), nth, values.end());
8    return std::is_sorted(values.begin(), values.end());
9}
10
11int main() {
12    for (int n = 1; n <= 40; ++n) {
13        std::vector<int> values;
14        for (int i = n; i >= 1; --i) {
15            values.push_back(i);
16        }
17
18        std::cout << n << ": " << is_sorted_after_nth(values) << '\n';
19    }
20}

On some platforms you may observe a threshold-like pattern. On others, the results may differ.

Why the Library Designers Do This

Algorithms in the standard library are judged by asymptotic complexity and practical performance, not by purity of implementation style. For tiny ranges, a full insertion sort can be faster than continuing with a more elaborate partition-based routine.

So if a library chooses to fully sort a tiny range inside nth_element, that is often a pragmatic optimization rather than a semantic statement about what nth_element means.

What You Should Do in Real Code

Use std::nth_element when you need:

• a median
• a percentile cutoff
• a top-k boundary
• partitioning around one position

Use std::sort when you actually need sorted order.

If your program happens to receive a sorted result after nth_element on some small inputs, treat that as an accident of implementation, not a guaranteed feature you can rely on.

Common Pitfalls

One common mistake is assuming that because a small test case came back sorted, nth_element sorts everything before and after nth. It does not guarantee that.

Another issue is benchmarking one compiler or library version and then treating the observed small-range cutoff as portable. It is not.

Developers also sometimes use nth_element and then perform binary-search-style logic on the result, forgetting that only partitioning is guaranteed, not sorted order.

Finally, if you truly need both the nth element and sorted order, call the algorithm that matches the stronger requirement instead of depending on a side effect that may disappear later.

Summary

• 'std::nth_element does not guarantee a fully sorted range.'
• Fully sorted results on tiny inputs are usually an implementation detail.
• Many STL implementations switch to simple small-range algorithms such as insertion sort.
• The exact cutoff is not standardized and can vary across libraries and versions.
• Use std::sort when sorted order is required, and treat any full sorting from nth_element as incidental.