Why should Insertion Sort be used after threshold crossover in Merge Sort
algorithm, divide-and-conquer, mergesort, quicksort, sorting
Solution
- Insertion sort is faster in practice, than bubblesort at least. Their asympotic running time is the same, but insertion sort has better constants (fewer/cheaper operations per iteration). Most notably, it requires only a linear number of swaps of pairs of elements, and in each inner loop it performs comparisons between each of n/2 elements and a "fixed" element that can be stores in a register (while bubble sort has to read values from memory). I.e. insertion sort does less work in its inner loop than bubble sort.
- The answer claims that 10000 n lg n > 10 n² for "reasonable" n. This is true up to about 14000 elements.
Problem
I have read everywhere that for divide and conquer sorting algorithms like `Merge-Sort` and `Quicksort`, instead of recursing until only a single element is left, it is better to shift to `Insertion-Sort` when a certain threshold, say 30 elements, is reached. That is fine, but why only `Insertion-Sort`? Why not `Bubble-Sort` or `Selection-Sort`, both of which has similar `O(N^2)` performance? `Insertion-Sort` should come handy only when many elements are pre-sorted (although that advantage should also come with `Bubble-Sort`), but otherwise, why should it be more efficient than the other two? And secondly, at this link, in the 2nd answer and its accompanying comments, it says that `O(N log N)` performs poorly compared to `O(N^2)` upto a certain `N`. How come? `N^2` should always perform worse than `N log N`, since `N > log N` for all N >= 2, right?