Anti-QuickSort

To sort a sequence of numbers, the widely used quicksort algorithm—QuickSort—is commonly employed. The following is a program that sorts an array $a$, using this algorithm.

var a : array [1..N] of integer;

procedure QSort(left, right : integer);

var m, i, j, t : integer;

begin

m := a[(left+right) div 2];

i := left; j := right;

repeat

while a[i] < m do inc(i); {first while}

while a[j] > m do dec(j); {second while}

if i <= j then

begin

t := a[i]; a[i] := a[j]; a[j] := t;

inc(i); dec(j);

end;

until i > j;

if j > left then QSort(left, j);

if i < right then QSort(i, right);

end;

begin

...

QSort(1, N);

end.

Although QuickSort is the fastest on average, there are cases in which it works very slowly. To evaluate the running time, consider the number of comparisons with elements of the array (i.e., the total number of comparisons in the first and second while statements). You are required to write a program that generates a test case in which QuickSort makes the greatest number of such comparisons.