Рекурсивный алгоритм сортировки Хоара

Приведем рекурсивный алгоритм сортировки массива на основе быстрой сортировки Хоара, который и на практике является одним из самых быстрых.

Задача. Пусть дан массив a[1]..a[n]. Рекурсивная процедура sort (l,r:integer) сортирует участок массива с индексами из полуинтервала (l,r] (т.е. a[l+1]..a[r]), не затрагивая остального массива.

procedure sort (l,r: integer);
 begin
 | if (l = r) then begin
 | | ничего делать не надо - участок пуст
 | end else begin
 | | выбрать случайное число s в полуинтервале (l,r]
 | | b := a[s]
 | | переставить элементы сортируемого участка так, чтобы
 | | сначала шли элементы, меньшие b - участок (l,ll]
 | | затем элементы, равные b - участок (ll,rr]
 | | затем элементы, большие b - участок (rr,r]
 | | sort (l,ll);
 | | sort (rr,r);
 | end;
 end;

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