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, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const INSERTION_THRESHOLD = 16;
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.insertionThreshold = INSERTION_THRESHOLD;
  function swap(i, j) {
    if (i === j) return;
    swap(i, j);
    const value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric('pairSwaps');
  }
  function compareAndSwap(i, j) {
    compare(i, j);
    if (arr[i] > arr[j]) swap(i, j);
  }
  function insertionSort(lo, hi) {
    recordMetric('insertionSortCalls');
    for (let i = lo + 1; i <= hi; i++) {
      const value = arr[i];
      let j = i;
      while (j > lo) {
        compare(j - 1, i);
        if (arr[j - 1] <= value) break;
        arr[j] = arr[j - 1];
        recordMetric('writeOperations');
        write(j, arr[j]);
        j--;
      }
      arr[j] = value;
      recordMetric('writeOperations');
      write(j, value);
    }
  }
  function partition(lo, hi) {
    recordMetric('partitionCalls');
    const mid = lo + (hi - lo >> 1);
    compareAndSwap(lo, mid);
    compareAndSwap(lo, hi);
    compareAndSwap(mid, hi);
    swap(mid, hi - 1);
    const pivotIndex = hi - 1;
    const pivot = arr[pivotIndex];
    let left = lo;
    let right = hi - 1;
    while (true) {
      do {
        left++;
        compare(left, pivotIndex);
      } while (arr[left] < pivot);
      do {
        right--;
        compare(right, pivotIndex);
      } while (arr[right] > pivot);
      if (left >= right) break;
      swap(left, right);
    }
    swap(left, pivotIndex);
    return left;
  }
  function sort(lo, hi) {
    while (lo < hi) {
      if (hi - lo + 1 <= INSERTION_THRESHOLD) {
        insertionSort(lo, hi);
        return;
      }
      const pivot = partition(lo, hi);
      checkpoint(Math.min(metrics.partitionCalls, n), n);
      if (pivot - lo < hi - pivot) {
        sort(lo, pivot - 1);
        lo = pivot + 1;
      } else {
        sort(pivot + 1, hi);
        hi = pivot - 1;
      }
    }
  }
  sort(0, n - 1);
  for (let i = 0; i < n; i++) markSorted(i);
  checkpoint(n, n);
}
 def quickSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def swap(i, j):
        if (i == j):
            return
        swap(i, j)
        value = arr[i]
        arr[i] = arr[j]
        arr[j] = value
        recordMetric("pairSwaps")

    def compareAndSwap(i, j):
        compare(i, j)
        if (arr[i] > arr[j]):
            swap(i, j)

    def insertionSort(lo, hi):
        recordMetric("insertionSortCalls")
        for i in range((lo + 1), (hi + 1)):
            value = arr[i]
            j = i
            while (j > lo):
                compare((j - 1), i)
                if (arr[(j - 1)] <= value):
                    break
                arr[j] = arr[(j - 1)]
                recordMetric("writeOperations")
                write(j, arr[j])
                j -= 1
            arr[j] = value
            recordMetric("writeOperations")
            write(j, value)

    def partition(lo, hi):
        recordMetric("partitionCalls")
        mid = (lo + ((hi - lo) >> 1))
        compareAndSwap(lo, mid)
        compareAndSwap(lo, hi)
        compareAndSwap(mid, hi)
        swap(mid, (hi - 1))
        pivotIndex = (hi - 1)
        pivot = arr[pivotIndex]
        left = lo
        right = (hi - 1)
        while True:
            while True:
                left += 1
                compare(left, pivotIndex)
                if not ((arr[left] < pivot)):
                    break
            while True:
                right -= 1
                compare(right, pivotIndex)
                if not ((arr[right] > pivot)):
                    break
            if (left >= right):
                break
            swap(left, right)
        swap(left, pivotIndex)
        return left

    def sort(lo, hi):
        while (lo < hi):
            if (((hi - lo) + 1) <= INSERTION_THRESHOLD):
                insertionSort(lo, hi)
                return
            pivot = partition(lo, hi)
            checkpoint((metrics.partitionCalls if metrics.partitionCalls <= n else n), n)
            if ((pivot - lo) < (hi - pivot)):
                sort(lo, (pivot - 1))
                lo = (pivot + 1)
            else:
                sort((pivot + 1), hi)
                hi = (pivot - 1)

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    INSERTION_THRESHOLD = 16
    metrics.insertionThreshold = INSERTION_THRESHOLD
    sort(0, (n - 1))
    for i in range(n):
        markSorted(i)
    checkpoint(n, n)
 #include <vector>
#include <algorithm>
void recordMetric(int name, int );
void swap(int i, int j);
void compareAndSwap(int i, int j);
void insertionSort(int lo, int hi);
int partition(int lo, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swap(int i, int j) {
    if((i == j)) {
        return;
    }
    swap(i, j);
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
}

void compareAndSwap(int i, int j) {
    compare(i, j);
    if((arr[i] > arr[j])) {
        swap(i, j);
    }
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            recordMetric("writeOperations");
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        recordMetric("writeOperations");
        write(j, value);
    }
}

int partition(int lo, int hi) {
    recordMetric("partitionCalls");
    int mid = (lo + ((hi - lo) >> 1));
    compareAndSwap(lo, mid);
    compareAndSwap(lo, hi);
    compareAndSwap(mid, hi);
    swap(mid, (hi - 1));
    int pivotIndex = (hi - 1);
    int pivot = arr[pivotIndex];
    int left = lo;
    int right = (hi - 1);
    while(1) {
        do {
            left++;
            compare(left, pivotIndex);
        } while((arr[left] < pivot));
        do {
            right--;
            compare(right, pivotIndex);
        } while((arr[right] > pivot));
        if((left >= right)) {
            break;
        }
        swap(left, right);
    }
    swap(left, pivotIndex);
    return left;
}

void sort(int lo, int hi) {
    while((lo < hi)) {
        if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
            insertionSort(lo, hi);
            return;
        }
        int pivot = partition(lo, hi);
        checkpoint(((metrics.partitionCalls) < (n) ? (metrics.partitionCalls) : (n)), n);
        if(((pivot - lo) < (hi - pivot))) {
            sort(lo, (pivot - 1));
            lo = (pivot + 1);
        } else {
            sort((pivot + 1), hi);
            hi = (pivot - 1);
        }
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    int metrics = educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swap(int i, int j) {
    if((i == j)) {
        return;
    }
    swap(i, j);
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
}

void compareAndSwap(int i, int j) {
    compare(i, j);
    if((arr[i] > arr[j])) {
        swap(i, j);
    }
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            recordMetric("writeOperations");
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        recordMetric("writeOperations");
        write(j, value);
    }
}

int partition(int lo, int hi) {
    recordMetric("partitionCalls");
    int mid = (lo + ((hi - lo) >> 1));
    compareAndSwap(lo, mid);
    compareAndSwap(lo, hi);
    compareAndSwap(mid, hi);
    swap(mid, (hi - 1));
    int pivotIndex = (hi - 1);
    int pivot = arr[pivotIndex];
    int left = lo;
    int right = (hi - 1);
    while(true) {
        do {
            left++;
            compare(left, pivotIndex);
        } while((arr[left] < pivot));
        do {
            right--;
            compare(right, pivotIndex);
        } while((arr[right] > pivot));
        if((left >= right)) {
            break;
        }
        swap(left, right);
    }
    swap(left, pivotIndex);
    return left;
}

void sort(int lo, int hi) {
    while((lo < hi)) {
        if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
            insertionSort(lo, hi);
            return;
        }
        int pivot = partition(lo, hi);
        checkpoint(Math.Min(metrics.partitionCalls, n), n);
        if(((pivot - lo) < (hi - pivot))) {
            sort(lo, (pivot - 1));
            lo = (pivot + 1);
        } else {
            sort((pivot + 1), hi);
            hi = (pivot - 1);
        }
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    int metrics = stats.educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} #include <stdio.h>
void recordMetric(int name, int );
void swap(int i, int j);
void compareAndSwap(int i, int j);
void insertionSort(int lo, int hi);
int partition(int lo, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void swap(int i, int j) {
    if((i == j)) {
        return;
    }
    swap(i, j);
    int value = arr[i];
    arr[i] = arr[j];
    arr[j] = value;
    recordMetric("pairSwaps");
}

void compareAndSwap(int i, int j) {
    compare(i, j);
    if((arr[i] > arr[j])) {
        swap(i, j);
    }
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            recordMetric("writeOperations");
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        recordMetric("writeOperations");
        write(j, value);
    }
}

int partition(int lo, int hi) {
    recordMetric("partitionCalls");
    int mid = (lo + ((hi - lo) >> 1));
    compareAndSwap(lo, mid);
    compareAndSwap(lo, hi);
    compareAndSwap(mid, hi);
    swap(mid, (hi - 1));
    int pivotIndex = (hi - 1);
    int pivot = arr[pivotIndex];
    int left = lo;
    int right = (hi - 1);
    while(1) {
        do {
            left++;
            compare(left, pivotIndex);
        } while((arr[left] < pivot));
        do {
            right--;
            compare(right, pivotIndex);
        } while((arr[right] > pivot));
        if((left >= right)) {
            break;
        }
        swap(left, right);
    }
    swap(left, pivotIndex);
    return left;
}

void sort(int lo, int hi) {
    while((lo < hi)) {
        if((((hi - lo) + 1) <= INSERTION_THRESHOLD)) {
            insertionSort(lo, hi);
            return;
        }
        int pivot = partition(lo, hi);
        checkpoint(((metrics.partitionCalls) < (n) ? (metrics.partitionCalls) : (n)), n);
        if(((pivot - lo) < (hi - pivot))) {
            sort(lo, (pivot - 1));
            lo = (pivot + 1);
        } else {
            sort((pivot + 1), hi);
            hi = (pivot - 1);
        }
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 16;
    int metrics = (*educational).metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, (n - 1));
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
    checkpoint(n, n);
} 
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.