Warum ist rekursive Mergesort schneller als iterative Mergesort? ⇐ Java

[Anonymous]

Ich habe gerade die beiden Algorithmen implementiert und ich war überrascht, als ich die Ergebnisse aufzeichnete! Rekursive Implementierung ist deutlich schneller als die iterative. Die Vorträge, die wir verwenden, um zu sehen, dass rekursiv langsamer ist wie in der faktoriellen Berechnung, aber hier scheint es nicht der Fall zu sein. Ich bin mir ziemlich sicher, dass meine Codes richtig sind. Was ist die Exprenation für dieses Verhalten? Br />
Wenn diese Codes nicht ausreichen, um zu verstehen /> Wie in Kommentaren gesagt, sollte ich Dinge vergleichen, die ähnlich sind. Jetzt ist die Merge -Methode iterativ und rekursiv gleich. < /P>

Code: Select all

private void merge(ArrayToSort 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  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++];
}
}
}
< /code>

Sortieren Sie rekursiv: < /p>

public void Sort(ArrayToSort array) {
T sub[] = (T[]) new Comparable[array.Length];
sort(array, sub, 0, array.Length - 1);
}

private InsertionSort insertionSort = new InsertionSort();
private void sort(ArrayToSort array, T[] sub_array, int min, int max) {
if (max 

private InsertionSort insertionSort = new InsertionSort();
public void Sort(ArrayToSort 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 

In dem neuen Diagramm können wir sehen, dass der Unterschied nun proportional ist ( à un fakteur près < /em>). Wenn jemand mehr Ideen hat ... Vielen Dank :)

Das neue * neue Handlung
 < /p>

Und hier ist meine Methode (Lehrer, die in der Tat) zu zeichnen: < /p>

for (int i = 0; i < nbSteps; i++) {
int N = startingCount + countIncrement * i;
for (ISortingAlgorithm algo : algorithms) {

long time = 0;
for (int j = 0; j < folds; j++) {
ArrayToSort 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());
}

}