View difference between Paste ID: hN2SnEfP and

-
+import java.io.IOException;
 import java.util.Arrays;
 import java.util.Random;
 
 public class Main {
 
 
     // сляние двух групп елементов одинокового размера
     void mergegroup(int a[], int n, int st1, int st2, int st3) {
       swapgroup(a, n, st1, st3);
                 int take1 = 0;
                 int take2 = 0;
                 for (int i = 0; i < 2 * n; i++) {
                         if ((take2 == n) || ((take1 < n) && (a[take1 + st3] < a[take2 + st2]))) {
                                 int t = a[st1 + i];
                                 a[st1 + i] = a[take1 + st3];
                                 a[take1 + st3] = t;
                                 take1++;
                         } else {
                                 int t = a[st1 + i];
                                 a[st1 + i] = a[take2 + st2];
                                 a[take2 + st2] = t;
                                 take2++;
                         }
                 }
         }
 
 
         // сортировка выбором
         void slowsort(int a[], int st, int en) {
                 for (int i = st; i < en; i++)
                         for (int j = i + 1; j < en; j++) {
                                 if (a[i] > a[j]) {
                                         int k = a[i];
                                         a[i] = a[j];
                                         a[j] = k;
                                 }
                         }
         }
 
 
         // обмен местами двух групп елементов одинакового размера
         void swapgroup(int a[], int n, int st1, int st2) {
                 for (int i = 0; i < n; i++) {
                         int k = a[st1 + i];
                         a[st1 + i] = a[st2 + i];
                         a[st2 + i] = k;
                 }
         }
 
 
         //слияние
         void merge(int[] a, int n) {
                 if (n <= 16) {
                         slowsort(a, 0, n);
                         return;
                 }
 
                 // разрез на группы длиной корень из n
                 int sizegroup = (int) Math.sqrt(n);
                 int remainder = n % sizegroup;
                 int numofgrp = n / sizegroup - 1;
 
                 // поиск конца первого массива
                 int posgap = 0;
                 while ((posgap < sizegroup * numofgrp) && (a[posgap] <= a[posgap + 1]))
                         posgap++;
 
                 // обмен группы содержащей конец первого массива  с последней и обьединение с остатком
                 swapgroup(a, sizegroup, numofgrp * sizegroup, posgap - posgap
                                 % sizegroup);
                 remainder += sizegroup;
 
                 // сортировка групп по первому елементу(в случае равенства по последнему)
                 for (int i = 0; i < numofgrp - 1; i++) {
                         int minnum = i;
                         for (int j = i + 1; j < numofgrp; j++)
                                 if ((a[j * sizegroup] < a[minnum * sizegroup])
                                         || ((a[j * sizegroup] == a[minnum * sizegroup])
                                         && (a[(j + 1) * sizegroup - 1] < a[(minnum + 1) *sizegroup-1])))
                                       minnum = j;
                         swapgroup(a, sizegroup, i * sizegroup, minnum * sizegroup);
                 }
 
                 // поочередное слияние групп
                 for (int i = 0; i < numofgrp - 1; i++) {
                         mergegroup(a, sizegroup, i * sizegroup, (i + 1) * sizegroup,
                                         numofgrp * sizegroup);
                 }
 
                 // сортировка конца массива
                 slowsort(a, n - 2 * remainder, n);
 
                 // поочередное слияние групп в обратную сторону
                 for (int i = n - 2 * remainder; i >= remainder; i -= remainder)
                         mergegroup(a, remainder, i - remainder, i, n - remainder);
 
                 // сортировка начала и конца массива
                 slowsort(a, 0, 2 * remainder);
                 slowsort(a, n - remainder, n);
         }
 
         // сортировка
         void sort(int[] a) {
                 int n = a.length;
                 for (int stp2 = 1; stp2 <= n; stp2 *= 2)
                         for (int i = 0; i < n; i += stp2) {
                                 int size = Math.min(n, i + stp2) - i;
                                 swapgroup(a, size, 0, i);      // для удобства реализации перемещаем
                                 merge(a, size);                // требуемый кусок масcива в начало
                                 swapgroup(a, size, 0, i);      // там его сортируем и возвращаем обратно
                         }
                 if (n > 16)
                         merge(a, n);
 
         }
 
 
         void testsort() throws IOException {
                 int n = 100000;
                 int[] a = new int[n];
                 Random st = new Random();
                 for (int i = 0; i < n; i++)
                         a[i] = st.nextInt();
                 int[] b = a.clone();
                 Arrays.sort(b);
                 sort(a);
                 for (int i = 0; i < n; i++)
                         if (a[i] != b[i])
                                 throw new AssertionError();
         };
 
 
         void run() throws IOException {
                 for (int i = 0; i < 10; i++) {
                         testsort();
                 }
         }
 
 
         public static void main(String[] args) throws IOException {
                 new Main().run();
         }
 }