Анти-QuickSort

Для сортування послідовності чисел широко використовується алгоритм швидкого сортування — QuickSort. Нижче наведена програма, що сортує масив $a$, використовуючи цей алгоритм.

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); {перший while}

while a[j] > m do dec(j); {другий 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.

Хоча QuickSort є найшвидшим у середньому, існують тести, де він працює дуже повільно. Для оцінки часу роботи будемо враховувати кількість порівнянь з елементами масиву (тобто суму порівнянь у першому і другому while). Необхідно написати програму, що генерує тест, на якому швидке сортування зробить найбільшу кількість таких порівнянь.