import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Arrays;
import java.util.Random;
 
class ThanosMeanArrays 
{   // Сортирует на месте (перезаписывает исходный массив)
    public static void thanosSortInPlace(int[] a) 
    { if (a == null || a.length < 2) return;
        int[] sorted = sortCopy(a);
        System.arraycopy(sorted, 0, a, 0, a.length);
    }

    // Сортирует Double на месте (перезаписывает исходный массив)
    public static void thanosDSortInPlace(double[] a) 
    { if (a == null || a.length < 2) return;
        double[] sorted = sortDoubleCopy(a);
        System.arraycopy(sorted, 0, a, 0, a.length);
    }
 
    // Рекурсия на подмассивах: 
    // сегмент -> (left,right) -> sort(left), sort(right) -> concat
    private static int[] sortCopy(int[] seg)  
    {   int n = seg.length;
        if (n < 2) return Arrays.copyOf(seg, n);
 
        // Быстрый выход: все элементы равны
        int mn = seg[0], mx = seg[0];
        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 Arrays.copyOf(seg, n);
 
        // Среднее текущего сегмента
        double c = sum / (double) n;
 
        // Подсчёт размеров левой и правой частей
        int cntL = 0, cntR = 0;
        for (int v : seg) if (v <= c) cntL++; else cntR++;
 
        // Заполняем подмассивы
        int[] left = new int[cntL];
        int[] right = new int[cntR];
        int iL = 0, iR = 0;

        for (int v : seg) 
        { if (v <= c) left[iL++] = v;
            else        right[iR++] = v;
        }
 
        // Рекурсия на подмассивах
        left  = sortCopy(left);
        right = sortCopy(right);
 
        // Склейка
        int[] out = new int[n];
        System.arraycopy(left,  0, out, 0, left.length);
        System.arraycopy(right, 0, out, left.length, right.length);
        return out;
    }

    // Рекурсия на подмассивах: 
    // сегмент -> (left,right) -> sort(left), sort(right) -> concat
    private static double[] sortDoubleCopy(double[] seg) 
    { int n = seg.length;
        if (n < 2) return Arrays.copyOf(seg, n);
 
        // Быстрый выход: все элементы равны
        double mn = seg[0], mx = seg[0];
        double sum = seg[0];

        for (int i = 1; i < n; i++) 
        { double v = seg[i];
            if (v < mn) mn = v;
            if (v > mx) mx = v;
            sum += v;
        }

        if (mn == mx) return Arrays.copyOf(seg, n);
 
        // Среднее текущего сегмента
        double c = sum / (double) n;
 
        // Подсчёт размеров левой и правой частей
        int cntL = 0, cntR = 0;
        for (double v : seg) if (v <= c) cntL++; else cntR++;
 
        // Заполняем подмассивы
        double[] left = new double[cntL];
        double[] right = new double[cntR];
        int iL = 0, iR = 0;

        for (double v : seg) 
        { if (v <= c) left[iL++] = v;
            else        right[iR++] = v;
        }
 
        // Рекурсия на подмассивах
        left  = sortDoubleCopy(left);
        right = sortDoubleCopy(right);
 
        // Склейка
        double[] out = new double[n];
        System.arraycopy(left,  0, out, 0, left.length);
        System.arraycopy(right, 0, out, left.length, right.length);
        return out;
    }
 
    //********** Универсальный random метод
    public static double[] generateDoubleRandomArray(int n, double min, double max) 
    {   Random rnd = new Random();
        double[] arr = new double[n];
 
        for (int i = 0; i < n; i++) 
        { arr[i] = min + rnd.nextDouble() * (max - min); // [min..max)
        }
        return arr;
    }

    public static int[] generateRandomArray(int n, int min, int max) 
    {   Random rnd = new Random();
        int[] arr = new int[n];
 
        for (int i = 0; i < n; i++) 
        {  arr[i] = rnd.nextInt(max - min + 1) + min; // [min..max]
        }
        return arr;
    }
    
    public static void main(String[] args) 
    {   int[] x = {5, 1, 9, 3, 7, 2, 2, 8, 4, 6};
        thanosSortInPlace(x);
        System.out.println(Arrays.toString(x));
        
        int[] arr = generateRandomArray(1000000,  0, 1000000);
        System.out.println("arr  before : ");
        int[] t1 = arr.clone();
        System.out.println("start Main int test code watch.");
        long t0 = System.nanoTime();
        thanosSortInPlace(t1);
         long t1n = System.nanoTime();
         System.out.println("stop watch.");
        System.out.printf("Thanos main int test code : %.2f ms%n", (t1n - t0) / 1e6);
        System.out.println("arr  sorted : ");
    }
}