title: Efficient way to count number of swaps to insertion sort an array of integers in increasing order
body: <p>Given an array of values of length n, is there a way to count the number of swaps that would be performed by insertion sort to sort that array in time better than O(n<sup>2</sup>)?</p>
  
  <p>For example :</p>
  
  <pre><code>arr[]={2 ,1, 3, 1, 2};  // Answer is 4.
  </code></pre>
  
  <p>Algorithm:</p>
  
  <pre><code>for i &lt;- 2 to N
  
      j &lt;- i
  
   while j &gt; 1 and a[j] &lt; a[j - 1]
  
         swap a[j] and a[j - 1]  //I want to count this   swaps?
  
         j &lt;- j - 1
  </code></pre>