Реализация быстрой сортировки

Используется рекурсивный подход и разбивка массива на partitions.
Сложность N*log(N), в худшем случае $N^2$

Формат ввода

В первой строке входного файла содержится число N — количество элементов массива (0 ≤ N ≤ ${10}^6$). Во второй строке содержатся N целых чисел a_i, разделенных пробелами ($-{10}^9$ ≤ a_i ≤ ${10}^9$).

Формат вывода

Результат сортировки, то есть N целых чисел, разделенных пробелами.