// TanosMeanLessMemory.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
 
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#include <string>    
#include <sstream>   
#include <cmath>     
// U
bool IsFinite(double v) {
    return !std::isnan(v) && !std::isinf(v);
}
 
class ThanosMeanLessMemory {
public:
    // --- int[] ---
    static void ThanosIntSortInPlace(std::vector<int>& a) {
        if (a.empty() || a.size() < 2) return;
        std::vector<int> sorted = SortNoExtraCopy(a);
        a = sorted; // Assign the sorted vector back to a
    }
 
private:
    static std::vector<int> SortNoExtraCopy(std::vector<int> seg) {
        int n = seg.size();
        if (n < 2) return seg;
 
        int mn = seg[0], mx = seg[0];
        long long sum = seg[0];
        for (int i = 1; i < n; i++) {
            int v = seg[i];
            if (v < mn) mn = v;
            if (v > mx) mx = v;
            sum += v;
        }
        if (mn == mx) return seg;
 
        double c = static_cast<double>(sum) / n;
 
        int cntL = 0;
        for (int v : seg) if (v <= c) cntL++;
        int cntR = n - cntL;
 
        std::vector<int> left(cntL);
        std::vector<int> right(cntR);
        int iL = 0, iR = 0;
        for (int v : seg) if (v <= c) left[iL++] = v; else right[iR++] = v;
 
        left = SortNoExtraCopy(left);
        right = SortNoExtraCopy(right);
 
        std::vector<int> outArr(n);
        std::copy(left.begin(), left.end(), outArr.begin());
        std::copy(right.begin(), right.end(), outArr.begin() + left.size());
        return outArr;
    }
 
public:
    // --- double[] ---
    static void ThanosDoubleSortInPlace(std::vector<double>& a) {
        if (a.empty() || a.size() < 2) return;
        std::vector<double> sorted = SortDoubleNoExtraCopy(a);
        a = sorted; // Assign the sorted vector back to a
    }
 
private:
    static std::vector<double> SortDoubleNoExtraCopy(std::vector<double> seg) {
        int n = seg.size();
        if (n < 2) return seg;
 
        bool allSame = true;
        for (int i = 1; i < n; i++) if (seg[i] != seg[0]) { allSame = false; break; }
        if (allSame) return seg;
 
        double sum = 0.0;
        int cntFinite = 0;
        for (double v : seg) if (IsFinite(v)) { sum += v; cntFinite++; }
        if (cntFinite == 0) return seg;
 
        double c = sum / cntFinite;
 
        int cntL = 0;
        for (double v : seg)
            if (std::isinf(v) && v < 0 || (IsFinite(v) && v <= c)) cntL++;
        int cntR = n - cntL;
 
        std::vector<double> left(cntL);
        std::vector<double> right(cntR);
        int iL = 0, iR = 0;
        for (double v : seg)
            if (std::isinf(v) && v < 0 || (IsFinite(v) && v <= c)) left[iL++] = v;
            else right[iR++] = v; // +Infinity и NaN здесь
 
        left = SortDoubleNoExtraCopy(left);
        right = SortDoubleNoExtraCopy(right);
 
        std::vector<double> outArr(n);
        std::copy(left.begin(), left.end(), outArr.begin());
        std::copy(right.begin(), right.end(), outArr.begin() + left.size());
        return outArr;
    }
 
public:
    // --- генераторы ---
    static std::vector<double> GenerateDoubleRandomArray(int n, double min, double max) {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_real_distribution<> dis(min, max);
 
        std::vector<double> arr(n);
        for (int i = 0; i < n; i++) arr[i] = dis(gen);
        return arr;
    }
 
    static std::vector<int> GenerateRandomArray(int n, int min, int max) {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(min, max);
 
        std::vector<int> arr(n);
        for (int i = 0; i < n; i++) arr[i] = dis(gen);
        return arr;
    }
};
 
template <typename T>
std::string Arr(const std::vector<T>& a) {
    std::string result = "[";
    for (size_t i = 0; i < a.size(); ++i) {
        result += std::to_string(a[i]);
        if (i < a.size() - 1) {
            result += ", ";
        }
    }
    result += "]";
    return result;
}
 
int main() {
    // Консоль в UTF-8 (Implementation depends on the OS and compiler, omitted for brevity)
 
    // int
    std::vector<int> arr = ThanosMeanLessMemory::GenerateRandomArray(1000000, 0, 1000000);
    auto tumbler = std::chrono::high_resolution_clock::now();
 
    // 1) Главный тестовый код
    std::vector<int> t1 = arr; // Copy the vector
    std::cout << "start Main test code watch." << std::endl;
    tumbler = std::chrono::high_resolution_clock::now();
    ThanosMeanLessMemory::ThanosIntSortInPlace(t1);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "stop watch." << std::endl;
    std::cout << "Thanos main test code : " << std::fixed << std::setprecision(2)
        << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
    std::cout << "_________" << std::endl;
 
    // 2) std::sort (internal)
    std::vector<int> t2 = arr; // Copy the vector
    std::cout << "start internal std::sort code watch." << std::endl;
    tumbler = std::chrono::high_resolution_clock::now();
    std::sort(t2.begin(), t2.end());
    end = std::chrono::high_resolution_clock::now();
    std::cout << "stop watch." << std::endl;
    std::cout << "std::sort , internal     : " << std::fixed << std::setprecision(2)
        << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
    std::cout << "_________" << std::endl;
 
    // double
    std::vector<double> arrD = ThanosMeanLessMemory::GenerateDoubleRandomArray(1000000, 0.0, 1000000.0);
 
    // 1) Главный тестовый код
    std::vector<double> tD1 = arrD; // Copy the vector
    std::cout << "start Main test double code watch." << std::endl;
    tumbler = std::chrono::high_resolution_clock::now();
    ThanosMeanLessMemory::ThanosDoubleSortInPlace(tD1);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "stop watch." << std::endl;
    std::cout << "Thanos main double test code : " << std::fixed << std::setprecision(2)
        << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
    std::cout << "_________" << std::endl;
 
    // 3) std::sort
    std::vector<double> tD3 = arrD; // Copy the vector
    std::cout << "start internal std::sort double code watch." << std::endl;
    tumbler = std::chrono::high_resolution_clock::now();
    std::sort(tD3.begin(), tD3.end());
    end = std::chrono::high_resolution_clock::now();
    std::cout << "stop watch." << std::endl;
    std::cout << "std::sort , double internal     : " << std::fixed << std::setprecision(2)
        << std::chrono::duration<double, std::milli>(end - tumbler).count() << " ms" << std::endl;
    std::cout << "_________" << std::endl;
 
    return 0;
}