Quicksort/Insertion Sort combo slower than just Quicksort?

Question

I run Quicksort 10 times, and get the average mean time. I do the same thing for Qicksort/Insertion sort combination, and it seems to be slower than just quicksort.

Here's the part of the code where I call InsertionSort

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) {
        int indexofpartition;
        if(max - min > 0) {
            if( (max - min) <= 10) {
                // Use InsertionSort now
                InsertionSort.sort(data);
                return;
            } else {
                indexofpartition = findPartition(data, min, max);

                OptQSort2(data, min, indexofpartition - 1);

                OptQSort2(data, indexofpartition + 1, max);
            }
        }

}

And the regular Quicksort is just the same as the above snippet, but without the if condition that calls InsertionSort.

FindPartition is as follows:

public static <T extends Comparable<? super T>> int findPartition(T[] data, int min, int max) {
    int left, right;
    T temp, partitionelement;
    int middle = (min + max)/2;

    partitionelement = data[middle];
    left = min;
    right = max;

    while(left < right) {
        while(data[left].compareTo(partitionelement) <= 0 && left < right)
            left++;

        while(data[right].compareTo(partitionelement) > 0)
            right--;

        if(left < right) {
            temp = data[left];
            data[left] = data[right];
            data[right] = temp;
        }
    }

The mean time for just Quicksort and OptSort2(which uses insertion sort) are

Sorted using QuickSort in: 3858841
Sorted using OptQSort2 in: 34359610

Any ideas why? Does the size of the sequence matter? I am using a 1000 element Integer[] array for this

Answer 1

In OptQSort2, for small partitions, you have the following function call:

InsertionSort.sort(data);

Is this supposed to insertion sort the small partition? It looks like you are insertion sorting the entire array. Shouldn't you pass the min and max indexes to InsertionSort?

Another option is to simply do no work on small partitions during OptQSort2. Then perform a single InsertionSort pass over the entire array after OptQSort2 has done its work.

Answer 2

You will need a much larger integer array for the test to be relevant. At this point, probably testing the if condition slows down your algorithm in the QS+IS case.

Test for a large amount of numbers and switch to IS when the size of the data is enough to fit in the L1 cache i.e. 32-64kb.

Answer 3

First suspect is obviously your insertion sort method. Does it really sort for example?

You will also need to test it many more than 10 times to warm up the JVM. And also to test them in both orders so one doesn't benefit from the warming up performed by the other. I would suggest 100 or 1000 tests. And they must all be on the same dataset too.

Answer 4

You should not call InsertionSort each time you have a subarray of at most 10 elements. Don't do anything:

public static <T extends Comparable<? super T>> void OptQSort2 (T[] data, int min, int max) {
    int indexofpartition;
        if( (max - min) > 10) {
            indexofpartition = findPartition(data, min, max);

            OptQSort2(data, min, indexofpartition - 1);

            OptQSort2(data, indexofpartition + 1, max);
        }

}

When you are finished call InsertionSort for the whole array.