        n |  sorted input, fixed pivot |  random input, fixed pivot |  sorted input, random pivot |   n(n-1)/2 |  2(n+1)H_n-4n
      100 |                       4950 |                        623 |                         634 |    4950.00 |       647.85
      500 |                     124750 |                       5146 |                        5144 |  124750.00 |      4806.41
     1000 |                     499500 |                      10452 |                       11176 |  499500.00 |     10985.91
     2000 |                    1999000 |                      22672 |                       23687 | 1999000.00 |     24729.83
     4000 |                    7998000 |                      55683 |                       57639 | 7998000.00 |     54988.87
