Я только что реализовал два алгоритма, и я был удивлен, когда я представил результаты!Рекурсивная реализация явно быстрее, чем итеративная.После этого я добавил сортировку вставки в сочетании с ними обоими, и результат был одинаковым.
В лекциях, которые мы используем, чтобы увидеть, что рекурсив медленнее, чем итеративный, как в факториальном вычислении, но здесь это не кажетсябыть так.Я уверен, что мои коды верны. Чем объясняется это поведение? Похоже, что java (10) автоматически реализует многопоточность в режиме рекурсии, потому что когда я отображаю небольшую анимацию, сортировка вставки работает параллельно с операциями слияния.
Если этих кодов недостаточно для понимания, вот мой github: Github
EDIT RELOADED Как сказано в комментариях, я должен сравнить похожие вещи, поэтому теперь метод слияниято же самое в итеративном и рекурсивном.
private void merge(ArrayToSort<T> array, T[] sub_array,
int min, int mid, int max) {
//we make a copy of the array.
if (max + 1 - min >= 0) System.arraycopy(array.array, min, sub_array, min, max + 1 - min);
int i = min, j = mid + 1;
for (var k = min; k <= max; k++) {
if (i > mid) {
array.array[k] = sub_array[j++];
} else if (j > max) {
array.array[k] = sub_array[i++];
} else if (sub_array[j].compareTo(sub_array[i]) < 0) {
array.array[k] = sub_array[j++];
} else {
array.array[k] = sub_array[i++];
}
}
}
Сортировка рекурсивная:
public void Sort(ArrayToSort<T> array) {
T sub[] = (T[]) new Comparable[array.Length];
sort(array, sub, 0, array.Length - 1);
}
private InsertionSort<T> insertionSort = new InsertionSort<>();
private void sort(ArrayToSort<T> array, T[] sub_array, int min, int max) {
if (max <= min) return;
if (max <= min + 8 - 1) {
insertionSort.Sort(array, min, max);
return;
}
var mid = min + (max - min) / 2;
sort(array, sub_array, min, mid);
sort(array, sub_array, mid + 1, max);
merge(array, sub_array, min, mid, max);
}
Сортировка итеративная:
private InsertionSort<T> insertionSort = new InsertionSort<>();
public void Sort(ArrayToSort<T> array) {
int length = array.Length;
int maxIndex = length - 1;
T temp[] = (T[]) new Comparable[length];
for (int i = 0; i < maxIndex; i += 8) {
insertionSort.Sort(array, i, Integer.min(i + 8 - 1, maxIndex));
}
System.arraycopy(array.array, 0, temp, 0, length);
for (int m = 8; m <= maxIndex; m = 2 * m) {
for (int i = 0; i < maxIndex; i += 2 * m) {
merge(array, temp, i, i + m - 1,
Integer.min(i + 2 * m - 1, maxIndex));
}
}
}
В новом графике мы видим, что теперьразница пропорциональна ( un facteur près ).Если у кого-то есть еще идеи ... Большое спасибо:)
Новый * новый сюжет 
А вот мой (на самом деле один из учителей) метод построения сюжета:
for (int i = 0; i < nbSteps; i++) {
int N = startingCount + countIncrement * i;
for (ISortingAlgorithm<Integer> algo : algorithms) {
long time = 0;
for (int j = 0; j < folds; j++) {
ArrayToSort<Integer> toSort = new ArrayToSort<>(
ArrayToSort.CreateRandomIntegerArray(N, Integer.MAX_VALUE, (int) System.nanoTime())
);
long startTime = System.currentTimeMillis();
algo.Sort(toSort);
long endTime = System.currentTimeMillis();
time += (endTime - startTime);
assert toSort.isSorted();
}
stringBuilder.append(N + ", " + (time / folds) + ", " + algo.Name() + "\n");
System.out.println(N + ", " + (time / folds) + ", " + algo.Name());
}
}