title: How is insertion better than mergesort in partially sorted array?
body: <p>I have to develop an algorithm that will be able to sort a n-element list, where the first (n- root(n)) elements are sorted. Yes, this is a homework question. </p>
  
  <p>After some <a href="http://en.wikipedia.org/wiki/Adaptive_sort" rel="nofollow noreferrer">research</a> on the internet and <a href="https://stackoverflow.com/questions/6771166/sorting-a-partially-sorted-array">stack-overflow</a>, I believe insertion sort and bubble sort work best for partially sorted array. This <a href="http://www.sorting-algorithms.com/" rel="nofollow noreferrer">link</a> clearly shows that insertion sort is better than merge sort. I have put insertion sort as the answer to my homework.</p>
  
  <p>However, I get confused when I start doing asymptotic complexity analysis.</p>
  
  <p>For insertion sort, we at least have to take a look at each element. If element is in unsorted order, we will have to do shifting/inversions. Thus, insertion sort will have O(n + m) where m is the total inversions. Or, we can also say that it has linear complexity O(n).</p>
  
  <p>For merge sort, we need to do mergesort for root(n) elements that are unsorted, which will give root(n)log(root (n)) complexity. Furthermore, we need to do merge with the sorted list (which will take O(n)). Thus, the complexity will be O(root(n) log (root (n)) + n) or O(n) since n dominates root(n) log (root(n)).</p>
  
  <p>How come both have the same asymptotic complexity? This is just my curiosity. I probably did mistake somewhere in the middle of complexity calculation. </p>
  
  <p>I am a student and still learning. I appreciate any help. Thanks.</p>