title: Least writes sort for a linked list python
body: <p>I have a linked list: <code>1 3 7 4 5 0 2 6</code>. I wish to sort it in the least number of moves/writes.</p>
  
  <p>I can only move elements of that list using a function <code>insertBetween(element, after, before)</code> which simply inserts <code>element</code> in between the <code>after</code> and <code>before</code> elements.</p>
  
  <p>For example, the first run might want to move 1 after 0 and before 2:
  <code>insertBetween(1, 0, 2)</code></p>
  
  <p>The list will now be <code>3 7 4 5 0 1 2 6</code>. </p>
  
  <p>Now it might want to move 7 to the end: <code>insertBetween(7, 6, None)</code></p>
  
  <p>The list will now be <code>3 4 5 0 1 2 6 7</code>.</p>
  
  <p>Now it might want to move 0 to the start: <code>insertBetween(0, None, 3)</code></p>
  
  <p>The list will now be <code>0 3 4 5 1 2 6 7</code>.</p>
  
  <p>The only priority for this sorting algorithm is the least number of uses of the function <code>insertBetween(element, after, before)</code>, since using it is extremely expensive. I wish to implement it in Python.</p>