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?