Quick Sort

High-performance divide and conquer

Quick Sort is one of the most widely used sorting algorithms. It works by picking a pivot element and partitioning the array so that elements smaller than the pivot go to the left, and larger ones go to the right. It then sorts the parts recursively.

Pivot Strategy

Comparisons

Swaps

Press "Start Sorting" to begin

Unsorted

Pivot

Comparing

Swapping

Final Position

Speed

The Power of the Pivot

Quick Sort is an in-place algorithm that uses very little extra memory. Its performance depends heavily on the choice of the pivot. If the pivot splits the array into two roughly equal halves, it achieves its optimal $O(n \log n)$ time.

Worst Case Sensitivity

The nightmare scenario for Quick Sort is an already sorted array with the first or last element as the pivot. This results in $O(n^2)$ complexity.

Cache Friendly

Unlike Merge Sort, Quick Sort works mostly with neighboring elements, making it extremely efficient on modern hardware caches.

Complexity

Best Case$O(n \log n)$

Average Case$O(n \log n)$

Worst Case$O(n^2)$

Space Complexity$O(\log n)$

StabilityUnstable

Partition Scheme

Pseudocode

JavaScript

1function partition(arr, low, high) {
2  pivot = arr[high];
3  i = low - 1;
4  for (j = low; j < high; j++) {
5    if (arr[j] < pivot) {
6      i++;
7      swap(arr, i, j);
8    }
9  }
10  swap(arr, i + 1, high);
11  return i + 1;
12}

Strategy

Modern implementations like std::sort in C++ use Introsort—a hybrid that starts with Quick Sort and switches to Heap Sort if the recursion depth exceeds a limit.

Implementations

Python (Lomuto)

Pseudocode

Python

1def quicksort(arr, low, high):
2    if low < high:
3        pi = partition(arr, low, high)
4        quicksort(arr, low, pi - 1)
5        quicksort(arr, pi + 1, high)
6 
7def partition(arr, low, high):
8    pivot = arr[high]
9    i = low - 1
10    for j in range(low, high):
11        if arr[j] <= pivot:
12            i += 1
13            arr[i], arr[j] = arr[j], arr[i]
14    arr[i+1], arr[high] = arr[high], arr[i+1]
15    return i + 1

JavaScript (ES6)

Pseudocode

JavaScript

1const quickSort = (arr) => {
2  if (arr.length <= 1) return arr;
3 
4  const pivot = arr[arr.length - 1];
5  const left = [];
6  const right = [];
7 
8  for (let i = 0; i < arr.length - 1; i++) {
9    if (arr[i] < pivot) left.push(arr[i]);
10    else right.push(arr[i]);
11  }
12 
13  return [...quickSort(left), pivot, ...quickSort(right)];
14};

The Power of the Pivot

Worst Case Sensitivity

The nightmare scenario for Quick Sort is an already sorted array with the first or last element as the pivot. This results in $O(n^2)$ complexity.

Cache Friendly

Unlike Merge Sort, Quick Sort works mostly with neighboring elements, making it extremely efficient on modern hardware caches.

1function partition(arr, low, high) { 2 pivot = arr[high]; 3 i = low - 1; 4 for (j = low; j < high; j++) { 5 if (arr[j] < pivot) { 6 i++; 7 swap(arr, i, j); 8 } 9 } 10 swap(arr, i + 1, high); 11 return i + 1; 12}

Implementations

Python (Lomuto)

Pseudocode

Python

1def quicksort(arr, low, high):
2    if low < high:
3        pi = partition(arr, low, high)
4        quicksort(arr, low, pi - 1)
5        quicksort(arr, pi + 1, high)
6 
7def partition(arr, low, high):
8    pivot = arr[high]
9    i = low - 1
10    for j in range(low, high):
11        if arr[j] <= pivot:
12            i += 1
13            arr[i], arr[j] = arr[j], arr[i]
14    arr[i+1], arr[high] = arr[high], arr[i+1]
15    return i + 1

JavaScript (ES6)

Pseudocode

JavaScript

1const quickSort = (arr) => {
2  if (arr.length <= 1) return arr;
3 
4  const pivot = arr[arr.length - 1];
5  const left = [];
6  const right = [];
7 
8  for (let i = 0; i < arr.length - 1; i++) {
9    if (arr[i] < pivot) left.push(arr[i]);
10    else right.push(arr[i]);
11  }
12 
13  return [...quickSort(left), pivot, ...quickSort(right)];
14};