title: Best sorting algorithm - Partially sorted linked list
body: <blockquote>
    <p>Problem- Given a sorted doubly link list and two numbers C and K. You need to decrease the info of node with data <code>K</code> by <code>C</code> and insert the new node formed at its correct position such that the list remains sorted.</p>
  </blockquote>
  
  <p>I would think of <em>insertion sort</em> for such problem, because, insertion sort at any instance looks like, shown bunch of cards, </p>
  
  <p><a href="https://i.stack.imgur.com/vLRvz.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/vLRvz.png" alt="enter image description here"></a></p>
  
  <p>that are partially sorted. For insertion sort, number of swaps is equivalent to number of inversions. Number of compares is equivalent to number of exchanges + (N-1).</p>
  
  <p>So, in the given problem(above), if node with data K is decreased by C, then the sorted linked list became partially sorted. <strong>Insertion sort is the best fit</strong>.</p>
  
  <p>Another point is, amidst selection of  sorting algorithm, if sorting logic applied for array representation of data holds best fit, then same sorting logic should holds best fit for linked list representation of same data.</p>
  
  <p>For this problem, Is my thought process correct in choosing insertion sort?</p>