Алгоритм быстрой сортировки является ярким примером использования идеи "разделяй и властвуй" и первым нетривиальным примером использования рекурсии. Кроме того, алгоритм быстрой сортировки — это самый простой алгоритм сортировки, который работает в среднем время N log N, где N — число элементов. Алгоритм сводит сортировку массива к разделению (partitioning) этого массива на две группы элементов и сортировке этих двух групп по отдельности.

Пусть нам нужно отсортировать участок массива A с p-го по q-й элемент включительно, будем называть этот участок подмассивом и обозначать как A[p..q].

* ШАГ 1: Возьмем элемент A[p] и "раскидаем" остальные элементы A[(p+1)..q] по разные стороны от него стороны — меньшие влево, большие --- вправо, то есть переставим элементы подмассива A[p..q] так, чтобы вначале шли элементы меньше либо равные A[p] потом элементы, больше либо равные A[p]. Назовет этот шаг разделением (partition).

* ШАГ 2: Пусть r есть новый индекс элемента A[p]. Тогда, если q - p > 2, вызовем функцию сортировки для подмассивов A[p..(r-1)] и A[(r+1)..q].

void quickSort(int* arr, int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}