Why using InsertionSort instead of Merge in MergeSort is averagely faster?

Question

Recently, I am fascinated with ShellSort algorithm idea by simply using InsertionSort in small sublist, then finally use InsertionSort for the whole list.

So, I thought why not combine MergeSort with InsertionSort (instead of using Merge() function, let use InsertionSort instead). Since InsertionSort is good at sorting partially sorted list and MergeSort idea is to merge two sorted list into one sorted list.

Then, I tested the MergeSort with merge() function and MergeSort with only InsertionSort() with array of 10,000,000 elements with random value. It turns out that MergeSort with InsertionSort() performs a few times faster than MergeSort with merge() function. Since coming up with accurate mathemetically proof is beyond my ability, I come here to seek for logical reason here. The following is what I want to confirm:

• Would MergeSort with merge() function will averagely outperform MergeSort with InsertionSort() for larger array or vise versa?
• Maybe my MergeSort with merge() function is inefficient.
• Will using ShellSort instead of InsertionSort inside MergeSort yields a faster performance?
• Since, MergeSort with InsertionSort isn't a bad idea, I believe there are already people who have discovered it. I wonder is there any unique algorithm name for it.

---

The following is the implementation of MergeSort()

public static void MergeSort(int[] array)
{
    int[] aux = new int[array.Length];
    MergeSort(array, aux, 0, array.Length - 1);
}

public static void MergeSort(int[] array, int[] aux, int low, int high) 
{
    if (low >= high) return;

    int mid = (low + high) / 2;

    MergeSort(array, aux, low, mid);
    MergeSort(array, aux, mid + 1, high);

    Merge(array, aux, low, mid, high);
}

protected static void Merge(int[] array, int[] aux, int low, int mid, int high) {
    // copy into aux array
    for (int i = low; i <= high; i++) aux[i] = array[i];

    // merge
    int j = low, k = mid + 1;
    for (int o = low; o <= high; o++) {
        if (j > mid)
            array[o] = aux[k++];
        else if (k > high)
            array[o] = aux[j++];
        else if (aux[k] < aux[j])
            array[o] = aux[k++];
        else
            array[o] = aux[j++];
    }
}

The following is MergeSort with InsertionSort()

public static void MergeInsertionSort(int[] array) 
{
    MergeInsertionSort(array, 0, array.Length - 1);
}

public static void MergeInsertionSort(int[] array, int low, int high) 
{
    if (low >= high) return;
    if (low + 1 == high) {
        // sort two elements
        if (array[low] > array[high]) {
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
    } else {
        int mid = (low + high) / 2;

        MergeInsertionSort(array, low, mid);
        MergeInsertionSort(array, mid + 1, high);

        // do insertion sort
        for (int i = mid + 1, j; i <= high; i++) {
            int ins = array[low];

            // move the element into correct position
            for (j = i - 1; (j >= low) && (ins < array[j]); j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = ins;
        }
    }
}

---

The following is a runnable code, you can test it on your computer: http://pastebin.com/4nh7L3H9

Answer 1

The problem here is that your insertion sort is broken, making it run much faster but return nonsensical output (all elements the same number by the looks of it). Here's an example of the tmp array after MergeInsertionSort is run (with the array size changed to 10):

1219739925
1219739925
1219739925
1219739925
1219739925
1219739925
1219739925
1219739925
1219739925
1275593566

Here's your code:

// do insertion sort
for (int i = mid + 1, j; i <= high; i++) {
    int ins = array[low];

    // move the element into correct position
    for (j = i - 1; (j >= low) && (ins < array[j]); j--) {
        array[j + 1] = array[j];
    }

    array[j + 1] = ins;
}

The problem is this line

    int ins = array[low];

This should be:

    int ins = array[i];

Once this is fixed you'll see that MergeSort is much more efficient than MergeInsertionSort (you'll have to decrease the array size so it runs in a reasonable length of time).

---

On another note, this took me a while to figure out, as I initially just put in a check to see if the output is sorted (which it is, but it isn't a sorted version of the input) instead of actually checking if it is a sorted version of the input. Wasn't until I looked at the output that I saw the problem.

Answer 2

You're not testing the same thing at all. Your Merge method uses an auxiliary array and the first thing it does is copy the initial array to the aux array before doing the actual merge work. So you end up doing twice as much work as you have to every time Merge is called.

You can eliminate that extra copy by doing some intelligent swapping of array and aux. That's more easily handled in the non-recursive implementation, but it's possible with the recursive version. I'll leave that as an exercise.

Your MergeInsertionSort method operates much differently. It's not doing a merge at all. It's just splitting up the array and doing insertion sorts on increasingly larger ranges.

The idea is to use insertion sort in order to reduce the overhead of merge when the range is small. Typically it looks like this:

public static void MergeSort(int[] array, int[] aux, int low, int high) 
{
    if (low >= high) return;

    if ((high - low) < MergeThreshold)
    {
        // do insertion sort of the range here
    }
    else
    {
        int mid = (low + high) / 2;

        MergeSort(array, aux, low, mid);
        MergeSort(array, aux, mid + 1, high);

        Merge(array, aux, low, mid, high);
    }
}

And you set MergeThreshold to the "small range" value that you've determined is appropriate. Typically that's in the range of 5 to 20, but you probably want to experiment with different values and different types (integers, strings, complex objects, etc.) to get a good all-around number.