По мотивам поста - завал java.util.Arrays.sort()

Я попробовал скормить данный int массив Arrays.sort() и ужаснулся - программа реально долго работает.

Но неужели всё так печально?

Оказалось - не совсем.

Далее для простоты привожу исходные коды методов, которые я использовал для проведения собственных "расследований".

Чтение в первых двух случаях шло из файла, который сгенерировал скрипт-убийца.

Последние 2 метода используют массив с рандомным заполнением. Для чистоты эксперимента, так сказать.

void solve() {

   int ar[] = new int[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = in.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}

  Start sorting 
  Sorted at 123324

void solve() {
   Integer ar[] = new Integer[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = in.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 530


void solve() {
   Random r = new Random();
   Integer ar[] = new Integer[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = r.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 624

void solve() {
   Random r = new Random();
   int ar[] = new int[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = r.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 234

Как видно - не всё так и страшно.

Если использовать Integer[] вместо int[] - будет использоваться сортировка слиянием, не имеющая худшего случая вообще (как и лучшего).