Алгоритмы. Быстрая сортировка

Алгоритм быстрой сортировки является алгоритмом "разделяй и властвуй". Средняя сложность его выполнения O(n*log(n)), а вот в худших случаях O(n^2) и это "неочень".

Зачем же он нужен, если сортировка слиянием всегда имеет отличное O(n*log(n))?
Ответ простой: для его выполнения требуется значительно меньше дополнительной памяти - почти не требуется.

Пример, отсортируем массив [35,33,42,10,14,19,27,44,26,31].
Шаги выполнения:

Пример выполнения 2-го и 3-го шага

1. Проверим базовый случай (base case) - начало любого рекурсивного алгоритма. Для быстрой сортировки: если элементов в массиве 0 или 1, то его сортировать не нужно. Если элементов больше, то переходим к шагу 2.
2. Выберем опорный элемент (pivot-элемент) в массиве. Это может быть любой элемент – первый, последний или случайный. Пусть в нашем случае опорным будет последний элемент - 31. 
3. Преобразуем массив. Относительно опорного q-элемента. Массив преобразуется следующим образом: [элементы <q, q, элементы >q]. Т.е. [26,27,19,10,14,31,33,44,35,42]
4. Рекурсивно выполним алгоритм на двух подмассивах - [l, q-1], [q+1, r]. Где l - это первый элемент, r - последний, q - опорный. 

В отличие от сортировки слиянием, основная логика этого алгоритма - выбор опорного элемента и преобразование массива, выполняется до дополнительных рекурсивных вызовов.

Сортируйте быстро, не сортируйте медленно.