How to find out the largest element number(array size), let insertion sort beat Merge sort?

Question

from wiki page of insertion sort:

Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, where insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.

the quote from wiki has one reason is that, the small lists from merge sort are not worse case for insertion sort.

I want to just ignore this reason.

I knew that if the array size is small, Insertion sort O(n^2) has chance to beat Merge Sort O(n log n).

I think(not sure) this is related to the constants in T(n)

Insertion sort: T(n) = c1n^2 +c2n+c3

Merge Sort: T(n) = n log n + cn

now my question is, on the same machine, same case (worse case), how to find out the largest element number, let insertion sort beat merge sort?

Answer 1

It's simple:

Take a set of sample arrays to sort, and iterate over a value k where k is the cutoff point for when you switch from merge to insertion.

then go

for(int k = 1; k < MAX_TEST_VALUE; k++) {
    System.out.println("Results for k = " + k);
    for(int[] array : arraysToTest) {
        long then = System.currentTimeMillis();
        mergeSort(array,k); // pass in k to your merge sort so it uses that
        long now = System.currentTimeMillis();
        System.out.println(now - then);
    }
}

For what it's worth, the java.util.Arrays class has this to say on the matter in its internal documentation:

/**
 * Tuning parameter: list size at or below which insertion sort will be
 * used in preference to mergesort or quicksort.
 */
private static final int INSERTIONSORT_THRESHOLD = 7;

/**
 * Src is the source array that starts at index 0
 * Dest is the (possibly larger) array destination with a possible offset
 * low is the index in dest to start sorting
 * high is the end index in dest to end sorting
 * off is the offset to generate corresponding low, high in src
 */
private static void mergeSort(Object[] src,
              Object[] dest,
              int low,
              int high,
              int off) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low &&
         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

In its primitive sequences, it also uses 7, although it doesn't use the constant value.

Answer 2

Typically, that's done by testing with arrays of varying size. When n == 10, insertion sort is almost certainly faster. When n == 100, probably not. Test, test, test, until your results converge.

I suppose it's possible to determine the number strictly through analysis, but to do so you'd have to know exactly what code is generated by the compiler, include instruction timings, and take into account things like the cost of cache misses, etc. All things considered, the easiest way is to derive it empirically.

Answer 3

Insertion sort usually beats merge sort for sorted (or almost sorted) lists of any size.

So the question "How to find out the largest element number(array size), let insertion sort beat Merge sort? " is not really correct.

edit: Just to get the downvoters of my back: The question could rephrased as:

1. "how to determine largest array size for which, on average, insertion sort beats merge sort". This usually is measured empirically by generating sample of arrays of small size and running implementations of both algorithms on them. glowcoder does that in his answer.
2. "what is the largest array size for which insertion sort in worst case performs better than merge sort" This is something that can be approximately answered by a simple calculation as IS has to do n insertions and n*(n-1) element movements (which are insertions) in worst case , while mergesort does always n*logn cell copies from one array to another. Since it will be relatively small number it doesn't even make sense to consider it.