Я просто оставлю здесь генератор теста: [Codeforces] [Ideone] [Pastebin]

UPD. Аналогичный пост про Java 6: http://codeforces.net/blog/entry/2296

UPD 2. Ссылка обновлена. Новый генератор работает немного быстрее. Однако, кажется, где-то есть ошибка, поэтому для некоторых размеров массива может генерироваться быстросортируемый массив. Всегда проверяйте, действительно ли сортировка работает медленно.

UPD 3. Ссылки еще раз обновлены. Теперь все почти идеально. Есть один недочет, который я пока не придумал, как обойти, но в целом генератор свою функцию выполняет.