fork download 
  1. import java.io.IOException;
  2. import java.util.Arrays;
  3. import java.util.Random;
  4.  
  5. public class Main {
  6.  
  7.  
  8.         // сляние двух групп елементов одинокового размера
  9.         void mergegroup(int a[], int n, int st1, int st2, int st3) {
  10.                 swapgroup(a, n, st1, st3);
  11.                 int take1 = 0;
  12.                 int take2 = 0;
  13.                 for (int i = 0; i < 2 * n; i++) {
  14.                         if ((take2 == n)
  15.                                         || ((take1 < n) && (a[take1 + st3] < a[take2 + st2]))) {
  16.                                 int t = a[st1 + i];
  17.                                 a[st1 + i] = a[take1 + st3];
  18.                                 a[take1 + st3] = t;
  19.                                 take1++;
  20.                         } else {
  21.                                 int t = a[st1 + i];
  22.                                 a[st1 + i] = a[take2 + st2];
  23.                                 a[take2 + st2] = t;
  24.                                 take2++;
  25.                         }
  26.                 }
  27.         }
  28.  
  29.  
  30.         // сортировка выбором
  31.         void slowsort(int a[], int st, int en) {
  32.                 for (int i = st; i < en; i++)
  33.                         for (int j = i + 1; j < en; j++) {
  34.                                 if (a[i] > a[j]) {
  35.                                         int k = a[i];
  36.                                         a[i] = a[j];
  37.                                         a[j] = k;
  38.                                 }
  39.                         }
  40.         }
  41.  
  42.  
  43.         // обмен местами двух групп елементов одинакового размера    
  44.         void swapgroup(int a[], int n, int st1, int st2) {
  45.                 for (int i = 0; i < n; i++) {
  46.                         int k = a[st1 + i];
  47.                         a[st1 + i] = a[st2 + i];
  48.                         a[st2 + i] = k;
  49.                 }
  50.         }
  51.  
  52.  
  53.         //слияние
  54.         void merge(int[] a, int n) {
  55.                 if (n <= 16) {
  56.                         slowsort(a, 0, n);
  57.                         return;
  58.                 }
  59.  
  60.                 // разрез на группы длиной корень из n
  61.                 int sizegroup = (int) Math.sqrt(n);
  62.                 int remainder = n % sizegroup;
  63.                 int numofgrp = n / sizegroup - 1;
  64.  
  65.                 // поиск конца первого массива
  66.                 int posgap = 0;
  67.                 while ((posgap < sizegroup * numofgrp) && (a[posgap] <= a[posgap + 1]))
  68.                         posgap++;
  69.  
  70.                 // обмен группы содержащей конец первого массива  с последней и обьединение с остатком
  71.                 swapgroup(a, sizegroup, numofgrp * sizegroup, posgap - posgap
  72.                                 % sizegroup);
  73.                 remainder += sizegroup;
  74.  
  75.                 // сортировка групп по первому елементу(в случае равенства по последнему)
  76.                 for (int i = 0; i < numofgrp - 1; i++) {
  77.                         int minnum = i;
  78.                         for (int j = i + 1; j < numofgrp; j++)
  79.                                 if ((a[j * sizegroup] < a[minnum * sizegroup])
  80.                                                 || ((a[j * sizegroup] == a[minnum * sizegroup]) && (a[(j + 1)
  81.                                                                 * sizegroup - 1] < a[(minnum + 1) * sizegroup
  82.                                                                 - 1])))
  83.                                         minnum = j;
  84.                         swapgroup(a, sizegroup, i * sizegroup, minnum * sizegroup);
  85.                 }
  86.  
  87.                 // поочередное слияние групп
  88.                 for (int i = 0; i < numofgrp - 1; i++) {
  89.                         mergegroup(a, sizegroup, i * sizegroup, (i + 1) * sizegroup,
  90.                                         numofgrp * sizegroup);
  91.                 }
  92.  
  93.                 // сортировка конца массива
  94.                 slowsort(a, n - 2 * remainder, n);
  95.  
  96.                 // поочередное слияние групп в обратную сторону 
  97.                 for (int i = n - 2 * remainder; i >= remainder; i -= remainder)
  98.                         mergegroup(a, remainder, i - remainder, i, n - remainder);
  99.  
  100.                 // сортировка начала и конца массива
  101.                 slowsort(a, 0, 2 * remainder);
  102.                 slowsort(a, n - remainder, n);
  103.         }
  104.  
  105.         // сортировка
  106.         void sort(int[] a) {
  107.                 int n = a.length;
  108.                 for (int stp2 = 1; stp2 <= n; stp2 *= 2)
  109.                         for (int i = 0; i < n; i += stp2) {
  110.                                 int size = Math.min(n, i + stp2) - i;  
  111.                                 swapgroup(a, size, 0, i);              // для удобства реализации перемещаем  
  112.                                 merge(a, size);                        // требуемый кусок масcива в начало
  113.                                 swapgroup(a, size, 0, i);              // там его сортируем и возвращаем обратно
  114.                         }
  115.                 if (n > 16)
  116.                         merge(a, n);
  117.  
  118.         }
  119.  
  120.  
  121.         void testsort() throws IOException {
  122.                 int n = 100000;
  123.                 int[] a = new int[n];
  124.                 Random st = new Random();
  125.                 for (int i = 0; i < n; i++)
  126.                         a[i] = st.nextInt();
  127.                 int[] b = a.clone();
  128.                 Arrays.sort(b);
  129.                 sort(a);
  130.                 for (int i = 0; i < n; i++)
  131.                         if (a[i] != b[i])
  132.                                 throw new AssertionError();
  133.         };
  134.  
  135.  
  136.         void run() throws IOException {
  137.                 for (int i = 0; i < 10; i++) {
  138.                         testsort();
  139.                 }
  140.         }
  141.  
  142.  
  143.         public static void main(String[] args) throws IOException {
  144.                 new Main().run();
  145.         }
  146. }
  147.  
Success #stdin #stdout 1.59s 213568KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/avUW3
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!