title: insertion, selection, bubble sorting analysis with inversion Robert Sedgewick
body: <p>I am reading algorithms by Robertsedwick by C++ on sorting</p>
  
  <blockquote>
    <p>Property 1: Insertion sort and bubble sort use a linear number of
    comparisions and exchanges for files with at most a constant number of
    inversions corresponding to each element.</p>
  </blockquote>
  
  <p>In another type of partially sorted file, we perhaps have appended a few elements to a sorted file  or have edited a few elements in a sorted file to change their kesy. Insetion sort is efficient menthod for such files; bubble and selection sort are not.</p>
  
  <blockquote>
    <p>Property 2: Insertion sort uses a linear number of comparisions and
    exchanges for files with atmost a constant number of elements having
    more than a constant number of corresponding inversions.</p>
  </blockquote>
  
  <p>My questions on above properties are</p>
  
  <ol>
  <li><p>I am not able to get difference between property 1 and property 2? Can any one explain me here?</p></li>
  <li><p>On what basis above for property 2 author mentioned insertion sort is best and not bubble and selection sort?</p></li>
  </ol>
  
  <p>It would be good if explained with example.</p>
  
  <p>Thanks for your time and help</p>