I just implemented the two algorithms and I was surprised when I plotted the results! Recursive implementation is clearly faster than the iterative one. After that, I added the insertion sort combined with both of them and the result was the same.
In the lectures we use to see that recursive is slower that iterative like in factorial calculation but here it doesn't seem to be the case. I pretty sure that my codes are right. What's the explenation for this behaviour? It look like java (10) implements automatically a multithread in recursion mode cause when I display the little animation the insertion sort works in parallel with merge operations.
If these codes are not enough to understand here is my github: Github
EDIT RELOADED As said in comments I should compare things that are similar so now the merge method is the same in iterative and recursive.
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++];
}
}
}
Sort Recursive:
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);
}
Sort Iterative:
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));
}
}
}
In the new plot we can see that now the difference is proportional (à un facteur près). If someone has any more ideas... Thanks a lot :)
The new * new plot

And here is my (teacher's one in fact) method to plot:
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());
}
}