PHP — написание простого quicksort

Не так давно мне пришлось искать новую работу в сфере веб разработки (PHP разработчик).
На одном из собеседований в достаточно крупную фирму, было некое подобие коллективного собеседования. Всех пригласили в одну аудиторию, раздали тесты и там же говорили с каждым кандидатом. Одним из вопросов, на котором «пролетели» большинство участников собеседования — алгоритм и реализация быстрой сортировки по массиву (quicksort). Некоторые не смогли реализовать, а некоторые даже написать его. В связи с этим, хочу помочь в понимании и написании и реализации этого алгоритма.

Итак, описание алгоритма:

• Необходимо выбрать элемент, на который будет опираться сортировка.
  Идеальный вариант — среднее число в массиве, тогда будет выполнена наименее емкая и наиболее быстрая сортировка, за меньшее количество проходов.
• Далее, опираясь на выбранный ранее центральный элемент, разделяем массив на часть которая больше этого элемента, и часть, которая меньше его.
  Делается это путем обмена элементов относительно выбранного центра.
• После прохода по массиву, рекурсивно вызываем функцию еще раз, для левой и правой части

Примерно так.

Далее приведу свой код, с комментариями, что бы лучше понять принцип действия

//Вызов функции
qsort($array);

/*
* Функция вычисляет количество элементов,
* тем самым подготавливая параметры для первого запуска,
* и запускает сам процесс.
*/

function qsort(&$array) {

$left = 0;
$right = count($array) - 1;

my_sort($array, $left, $right);

}

/*
* Функция, непосредственно производящая сортировку.
* Так как массив передается по ссылке, ничего не возвращает.
*/

function my_sort(&$array, $left, $right) {

//Создаем копии пришедших переменных, с которыми будем манипулировать в дальнейшем.
$l = $left;
$r = $right;

//Вычисляем 'центр', на который будем опираться. Берем значение ~центральной ячейки массива.
$center = $array[(int)($left + $right) / 2];

//Цикл, начинающий саму сортировку
do {

//Ищем значения больше 'центра'
while ($array[$r] > $center) {
$r--;
}

//Ищем значения меньше 'центра'
while ($array[$l] < $center) {
$l++;
}

//После прохода циклов проверяем счетчики циклов
if ($l <= $r) {

//И если условие true, то меняем ячейки друг с другом.
list($array[$r], $array[$l]) = array($array[$l], $array[$r]);

//И переводим счетчики на следующий элементы
$l++;
$r--;
}

//Повторяем цикл, если true
} while ($l <= $r);

if ($r > $left) {
//Если условие true, совершаем рекурсию
//Передаем массив, исходное начало и текущий конец
my_sort($array, $left, $r);
}

if ($l < $right) {
//Если условие true, совершаем рекурсию
//Передаем массив, текущие начало и конец
my_sort($array, $l, $right);
}

//Сортировка завершена

}


Конечно же, этот алгоритм применяется во многих других языках программирования, и думаю спрашивать его могут не только на собеседованиях PHP разработчиков, потому надеюсь, я кому то помогу.