title: Why should Insertion Sort be used after threshold crossover in Merge Sort
body: <p>I have read everywhere that for divide and conquer sorting algorithms like <code>Merge-Sort</code> and <code>Quicksort</code>, instead of recursing until only a single element is left, it is better to shift to <code>Insertion-Sort</code> when a certain threshold, say 30 elements, is reached. That is fine, but why only <code>Insertion-Sort</code>? Why not <code>Bubble-Sort</code> or <code>Selection-Sort</code>, both of which has similar <code>O(N^2)</code> performance? <code>Insertion-Sort</code> should come handy only when many elements are pre-sorted (although that advantage should also come with <code>Bubble-Sort</code>), but otherwise, why should it be more efficient than the other two?</p>
  
  <p>And secondly, at <a href="https://stackoverflow.com/questions/8101546/why-is-insertion-sort-better-than-quick-sort-for-small-list-of-elements">this link</a>, in the 2nd answer and its accompanying comments, it says that <code>O(N log N)</code> performs poorly compared to <code>O(N^2)</code> upto a certain <code>N</code>. How come? <code>N^2</code> should always perform worse than <code>N log N</code>, since <code>N &gt; log N</code> for all N >= 2, right?</p>