title: Counting inversions to see if an array is partially sorted
body: <p>The definition of a sorted array below is from Algorithm book by Robert Sedgewick and Kevin Wayne. </p>
  
  <blockquote>
    <p>An array is partially sorted if the number of inversions is &lt;= cN</p>
  </blockquote>
  
  <p>Shouldn't there be a limit to how high c can be? Couldn't I technically make c = 1000000000 and now a lot of unsorted arrays would be counted as partially sorted when they shouldn't be? I know that setting a high c is not smart, but shouldn't be some kind of range? </p>
  
  <p>Here is an example of a worst case. </p>
  
  <pre><code>D C B A
  </code></pre>
  
  <p>Inversion counts</p>
  
  <p>1 (d, c)</p>
  
  <p>2 (d, b)</p>
  
  <p>3 (d, a)</p>
  
  <p>4 (c, b)</p>
  
  <p>5 (c, a )</p>
  
  <p>6 (b , a)</p>
  
  <p>For an array of size 4, 6 items. That's totally linear if c = 2 and 6 &lt; 4*2 </p>
  
  <p>When do we hit the N^2 range? </p>