Быстрая сортировка или Quicksort. Основной алгоритм      Выберем случайным образом какой-то элемент х и просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х. Поменяем их местами и продолжим процесс просмотра с обменом, поука эти элементы не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х. К получившимся частям рекурсивно применяем ту же процедуру. Пример на Си номер 1. Неэффективно, но просто для понимания. Улучшения      На практике для увеличения быстроты, но не асимптотики, можно произвести несколько улучшений:      1. В качестве центрального для функции partition выбирается элемент, расположенный в середине. Такой выбор улучшает оценку среднего времени работы, если массив упорядочен лишь частично. Наихудшая для этой реализации ситуация возникает в случае, когда каждый раз при работе partition в качестве центрального выбирается максимальный или минимальный элемент.      2. Для коротких массивов вызывается сортировка вставками. Из-за рекурсии и других "накладных расходов" быстрый поиск оказывается не столь уж быстрым для коротких массивов. Поэтому, если в массиве меньше 12 элементов, вызывается сортировка вставками. Пороговое значение не критично - оно сильно зависит от качества генерируемого кода.      3. Если последний оператор функции является вызовом этой функции, говорят о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае лучше используется стек.      4. После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек. Требования к памяти уменьшаются с n до log n. Пример, входящий в стандартную реализацию Си использует многие из этих улучшений.