Why is recursive MergeSort faster than iterative MergeSort?

Question

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());
    }

}

Answer 1

I don't think I have an answer because I didn't try your code. I will give you thoughts:

a) CPU have L1 cache and instruction prefetching. The recursive version may have better locality of references when all the sorts are done and it is finishing with a bunch of merges while poping all frames (of for other cpu optimzation reasons)

b) Meanwhile the JIT compiler does crazy things to recursion, particularly due to tail recursion and inlining. I suggest you try without JIT compiler just for fun. Also might want to try changing the thresholds for JIT compilation, so it gets JIT compiled faster for minimizing the warmup time.

c) system.arraycopy is a native method and despite being optimized, it should have overhead.

d) the iterative version seems to have more arithmetics in the loops.

e) that is an attempt at micro-benchmarking. you need to factor out the GC and have tests running dozens if not hundreds of times. Read up on JMH. Also try different GCs and -Xmx.