C++ Basics: Select a Median Without Sorting Every Element

Use std::nth_element to select the middle value of an odd-sized sample.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as nth-element-median-demo.cpp:

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> samples{9, 1, 7, 3, 5};
    if (samples.empty()) return 1;
    const auto middle = samples.begin() + samples.size() / 2;
    std::nth_element(samples.begin(), middle, samples.end());
    std::cout << "Median: " << *middle << '\n';
    std::cout << "Count: " << samples.size() << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic nth-element-median-demo.cpp -o nth-element-median-demo &&
./nth-element-median-demo

Observed output:

Median: 5
Count: 5

Read the result

The middle position contains 5, the value that would occupy that position in a fully sorted copy. The algorithm rearranges the sample in place but does not promise sorted order on either side. Printing only the selected value avoids depending on an unspecified arrangement.

Apply it carefully

Check for an empty range before dereferencing the selected position. For an even number of samples, size()/2 selects the upper middle value; it does not compute the average of the two middle values. Decide the statistical definition and overflow policy separately. The ordinary overload has average linear complexity and requires random-access iterators.

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- nth-element-median-demo.cpp nth-element-median-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.