title: Generating data to test sorting algorithm
body: <p>I would like to generate data to test sorting algorithms with. This accomplishes two things:</p>
  
  <ol>
  <li>Find bugs. The output could easily be checked if it was in fact sorted correctly</li>
  <li>Profile the code and find which situations take longer for which parts.</li>
  </ol>
  
  <p>I asked the question <a href="https://stackoverflow.com/questions/25295265/how-do-you-test-speed-of-sorting-algorithm">How do you test speed of sorting algorithm?</a> awhile ago, but this question focuses particularly on generating the data.</p>
  
  <p>I am thinking of</p>
  
  <ol>
  <li>sorted</li>
  <li>reverse sorted</li>
  <li>random</li>
  <li>sorted but then make <code>n</code> inversions in randomly selected elements and see how changing <code>n</code> affects the run time</li>
  </ol>
  
  <p>Any suggestions? Do any frameworks exist that would make this easier? I'm thinking JUnit could be useful. </p>
  
  <p>In this question on <a href="https://cs.stackexchange.com/questions/11836/how-to-measure-sortedness">comp sci se</a> an answer makes it sound like adding inversions and counting them doesn't mean much:</p>
  
  <blockquote>
    <p>The number of inversions might work for some cases, but is sometimes
    insufficient. An example given in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017" rel="nofollow noreferrer">[3]</a> is the sequence </p>
    
    <p>$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n,
    1, \ldots, \lfloor n/2 \rfloor \rangle$$</p>
    
    <p>that has a quadratic number of inversions, but only consists of two
    ascending runs. It is nearly sorted, but this is not captured by
    inversions.</p>
  </blockquote>
  
  <p>I'm not particularly strong in math and don't understand how the example illustrates what's wrong with counting the number of inversions? Is it just academic? How does it make sense to say "quadratic number of inversions"?</p>