median without sort

How easy is it to find the median of a list of numbers?
Let’s see what c++ has to offer. It’s surprising that most places on the internet don’t recommend this solution, and rather rely on sorting. Below is an example solution, with O(n * log n) complexity.

double findMedian(int arr[], int n)
{

    // first sort the array
    sort(arr, arr + n);

    // Check if the number is even or odd
    if (n % 2 != 0) {
        // If number of element is odd, return the middle
        // element
        return arr[n / 2];
    }
    else {
        // If number of element is even, return the average
        // of the two middle elements
        return (arr[(n - 1) / 2] + arr[n / 2]) / 2.0;
    }
}

If you ask a good llm or look for it, you can find the more optimal O(n) solution.

#include <algorithm>
#include <vector>

double findMedian(std::vector<int>& nums) {
    int n = nums.size();
    if (n % 2 == 0) {
        std::nth_element(nums.begin(), nums.begin() + n/2 - 1, nums.end());
        std::nth_element(nums.begin(), nums.begin() + n/2, nums.end());
        return (nums[n/2 - 1] + nums[n/2]) / 2.0;
    } else {
        std::nth_element(nums.begin(), nums.begin() + n/2, nums.end());
        return nums[n/2];
    }
}

how does the std::nth_element method work?

The std::nth_element method allows us to partially sort elements in a container based on a specific position. It takes three parameters: the starting and ending iterators of the range, and an iterator pointing to the element we want to place at its final sorted position. This method rearranges the elements so that all elements before the specified iterator are smaller than or equal to it, and all elements after it are greater.

It achieves this by using a variation of the QuickSelect algorithm known as Introselect, which combines the efficiency of QuickSort with the guaranteed worst-case performance of median of medians. This combination makes it a powerful tool for sorting(partially) elements efficiently.

A slight optimization in the case of even sized vectors could be

#include <algorithm>
#include <vector>

double findMedian(std::vector<int>& nums) {
    int n = nums.size();
    if (n % 2 == 0) {
        std::nth_element(nums.begin(), nums.begin() + n/2 - 1, nums.end());
        int right = *std::min_element(nums.begin() + n/2, nums.end());
        return (nums[n/2 - 1] + right) / 2.0;
    } else {
        std::nth_element(nums.begin(), nums.begin() + n/2, nums.end());
        return nums[n/2];
    }
}

I’d love to know if there is a better/cleaner/more-optimal solution out there.