Как найти медиану неотсортированного массива (без использования дополнительного массива)

//------------------------------------------------------поиск медианы
#include <iostream>
 
double Max (double *arr, int N)
{
    double max = arr[0];
    for (int i = 1; i<N; i++)
        if (arr[i] > max)
            max = arr[i];
 
    return max;
}
 
double Min (double *arr, int N)
{
    double min = arr[0];
    for (int i = 1; i<N; i++)
        if (arr[i] < min)
            min = arr[i];
 
    return min;
}
 
bool SearchByMin (double *arr, int N, double &mediana)
{
    double A = Min (arr, N);
    double B = Max (arr, N);
    
    for (int i = 0; i< N/2 + 1; i++)
    {
        if (A == B)
        {
            mediana = A;
            return true;
        }
        
        double C = (A+B) / 2.;
        int count = 0;
        double M = A;
        
        for (int j = 0; j < N; j++)
        {   
            if (arr[j] <= C) 
            {   
                count++;
                if (arr[j] > M)
                    M = arr[j];
            }
            if (count == N/2 + 1 && arr[j] == M)
            {
                mediana = M;
                return true;
            }
        }
        if (count > N/2 + 1)
            B = M;
        else if (count < N/2 + 1)
            A = M;
        else
        {
            mediana = M;
            return true;
        }
    }
    return false;
}
 
bool SearchByMax (double *arr, int N, double &mediana)
{
    double A = Min (arr, N);
    double B = Max (arr, N);
    
    for (int i = 0; i< N/2 + 1; i++)
    {
        if (A == B)
        {
            mediana = A;
            return true;
        }
        
        double C = (A+B) / 2.;
        int count = 0;
        double M = B;
        for (int j = 0; j < N; j++)
        {   
            if (arr[j] >= C) 
            {   
                count++;
                if (arr[j] < M)
                    M = arr[j];
            }
            if (count == N/2 + 1 && arr[j] == M)
            {
                mediana = M;
                return true;
            }
        }
        if (count > N/2 + 1)
            B = M;
        else if (count < N/2 + 1)
            A = M;
        else
        {
            mediana = M;
            return true;
        }
    }
    return false;
}
 
//----------------------------------------------------------------------------
int main()
{   
    double arr[] = {1,2,3,3,3,3,2,2,2,2,3};
    int N = sizeof(arr) / sizeof(double);
 
    double mediana = -1;
    if (!SearchByMin (arr, N, mediana))
        SearchByMax (arr, N, mediana);
 
    std::cout << mediana;
    
    std::cin.sync(); std::cin.get();
    return 0;
}
//-----------------------------------------------------------------------------

/////////////////////////////////////////////////////////////////////////////////////////
//В массиве содержится нечетное количество элементов 2n+1 элементов. Нужно найти n+1 
//по величине элемент, т.е. медиану массива и группу элементов с первыми n значениями, 
//т.е. если бы массив был упорядочен, то этот элемент находился бы в центре. Найти этот 
//элемент и левую половину. Вывести это на экран. Массив должен остаться в исходном состоянии. 
//Минимальное использование количества памяти.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector < double    >   T_numbers;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_is_mediana_of
{
    //-----------------------------------------------------------------------------------
    T_numbers  const    &   numbers_;
    //-----------------------------------------------------------------------------------
    T_is_mediana_of( T_numbers  const   &   numbers )
        :
        numbers_( numbers )
    {}
    //-----------------------------------------------------------------------------------
    bool    operator()  ( double    d )
    {
        size_t  less_count      =   0;
        size_t  great_count     =   0;
 
        for( size_t  i = 0; i < numbers_.size(); ++i )
        {
            if( numbers_[i]     <   d )
            {
                ++less_count;
            }
 
            if( numbers_[i]     >   d )
            {
                ++great_count;
            }
 
            if  (
                        less_count      >   numbers_.size() / 2
                    ||  great_count     >   numbers_.size() / 2
                )
            {
                return  false;
            }
        }//for
 
        return  true;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
double  get_mediana_of( T_numbers  const   &   numbers )
{
    return  *   std::find_if
                    (
                        numbers.begin       (),
                        numbers.end         (),
                        T_is_mediana_of     ( numbers )
                    );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    int     n   =   0;
 
    do
    {
        std::cout   <<  "Введите нечетный размер массива: ";
        std::cin    >>  n;
    }
    while   (
                    n           <   1
                ||  n   %   2   ==  0
            );
 
    std::cout   <<  "Введите "
                <<  n
                <<  " чисел:"
                <<  std::endl;
 
    T_numbers   numbers(n);
 
    std::generate
        (
            numbers.begin   (),
            numbers.end     (),
 
            []              ()  ->  double
            {
                std::cout   <<  "-> ";
                double  d   =   0;
                std::cin    >>  d;
                return  d;
            }
        );
 
    std::cout   <<  std::endl
                <<  "Медиана = "
                <<  get_mediana_of( numbers )
                <<  std::endl;
 
    system("pause");
}