Мой нелепый алгоритм в оп можно легко объяснить в словах:
1) Находим среднее значение в массиве;
2) Создаём два вспомогательных массива;
3) Значения в исходном массиве, которые меньше среднего, помещаем в первый вспомогательный массив, а которые больше — во второй;
4) Рекурсивно сортируем оба вспомогательных массива;
5) Переливаем в исходный массив сначала первый вспомогательный, потом второй;
6) Удаляем вспомогательные массивы.
А вы могли бы так же просто изложить стандартный алгоритм быстрой сортировки со схемой Хоара?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.