Quick Sort — VisualAlgorithms Docs

How it works

Quick Sort picks a pivot, partitions the array so that everything smaller sits left of the pivot and everything larger sits right, then recurses into each side. The pivot lands in its final position after each partition.

With a good pivot the partitions are balanced and the algorithm runs in O(n log n); a degenerate pivot on already-sorted data can degrade to O(n^2), which is why real implementations randomize or use median-of-three pivots.

Implementation

      
 function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i+1], arr[hi]] = [arr[hi], arr[i+1]];
  quickSort(arr, lo, i);
  quickSort(arr, i + 2, hi);
} def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    quick_sort(arr, lo, i)
    quick_sort(arr, i + 2, hi) void quickSort(vector<int>& arr, int lo, int hi) {
  if (lo >= hi) return;
  int pivot = arr[hi], i = lo - 1;
  for (int j = lo; j < hi; j++)
    if (arr[j] < pivot)
      swap(arr[++i], arr[j]);
  swap(arr[i+1], arr[hi]);
  quickSort(arr, lo, i);
  quickSort(arr, i + 2, hi);
} void QuickSort(int[] arr, int lo, int hi) {
  if (lo >= hi) return;
  int pivot = arr[hi], i = lo - 1;
  for (int j = lo; j < hi; j++)
    if (arr[j] < pivot) {
      i++;
      (arr[i], arr[j]) = (arr[j], arr[i]);
    }
  (arr[i+1], arr[hi]) = (arr[hi], arr[i+1]);
  QuickSort(arr, lo, i);
  QuickSort(arr, i + 2, hi);
} void quickSort(int arr[], int lo, int hi) {
  if (lo >= hi) return;
  int pivot = arr[hi], i = lo - 1;
  for (int j = lo; j < hi; j++)
    if (arr[j] < pivot) {
      i++;
      int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
    }
  int t = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = t;
  quickSort(arr, lo, i);
  quickSort(arr, i + 2, hi);
} 

Advantages

Fastest general-purpose comparison sort in practice for in-memory arrays.
In-place with only O(log n) stack space.
Very cache-friendly due to its sequential partition scans.

Disadvantages

Worst case is O(n^2) without pivot safeguards.
Not stable in its classic form.

When to use it

The default for unstable, in-memory sorting of primitives. Use IntroSort (Quick Sort with a heapsort fallback) when you need the average-case speed but a worst-case guarantee.