Сортировка Хоара (1962 г.)

 Это, по-видимому, наиболее популярный в мире метод внутренней сортировки. Установим указатели i и j на начало и конец таблицы. После сравнения ключей t_i, t_j изменяется один из индексов – i или j (увеличивается i или уменьшается j). Первым изменяется j. Если t_i > t_j, то ключи меняются местами и переключаемся на изменение противоположного указателя. Процесс продолжается до тех пор, пока указатели не встретятся. Пример выполнения процесса изображен на рисунке. Заметим, что ключ 7 участвовал во всех сравнениях. Все ключи слева от него меньше его, все ключи справа – больше его, а сам ключ 7 занял свое окончательное положение. Рассмотренный процесс назовем разделением.
  Теперь можно применить тот же самый процесс к левой и правой части разделенной таблицы. Оценим быстродействие алгоритма в наилучшем и наихудшем случае. В лучшем случае каждый отрезок разделяется точно посередине и всего разделений log₂N. В каждом отрезке проходятся все элементы, то есть для всех отрезков – N элементов. Таким образом, время оказывается пропорциональным Nlog₂N. В худшем случае массив ключей уже упорядочен. Каждое разделение создает два отрезка, в один из них входит 1 ключ, в другой – все остальные, следовательно, число разделений равно N и время сортировки пропорционально N². Ситуацию можно поправить выбором разделяющего ключа одним из двух способов:
 1. выбираем ключ со случайным номером на отрезке m…n
 2. выбираем медиану из трех ключей t_m, t_(m+n)/2, t_n.
Сортировка Хоара включена в библиотеки практически для всех компиляторов. Ниже приведён прототип функции qsort, которая ее реализует.
void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *, const void *));
Параметры:
 base - адрес начала таблицы
 nelem - число записей в таблице
 width - число байт в записи
 fcmp - указатель на функцию, выполняющую сравнение ключей