Sorting Algorithm Visualizer
Speed:
Unsorted
Comparing
Pivot
Sorted
Length:
Quick Sort
An efficient, divide-and-conquer sorting algorithm that works by selecting a 'pivot' element and partitioning the array around the pivot.

Statistics

Iterations
0
Swaps
0

Complexity Analysis

Case
Best
Average
Worst
Time
O(n log n)
O(n log n)
O(n²)
Space
O(log n)

How It Works

  1. Choose a pivot element from the array
  2. Partition the array: items less than the pivot go to the left, items greater go to the right
  3. The pivot is now in its final sorted position
  4. Recursively apply the above steps to the sub-arrays on the left and right of the pivot
  5. The base case is when a sub-array has 0 or 1 elements (already sorted)

Best (O(n log n))

When the pivot always divides the array into nearly equal halves, quick sort achieves its best performance.

Average (O(n log n))

For random arrays, quick sort is very efficient with O(n log n) time complexity.

Worst (O(n²))

When the pivot is always the smallest or largest element (e.g., in already sorted arrays), quick sort degrades to O(n²) performance.

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Find pivot element such that
    // elements smaller than pivot are on the left
    // elements greater than pivot are on the right
    const pivotIndex = partition(arr, low, high);

    // Recursively sort elements before and after pivot
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }

  return arr;
}

function partition(arr, low, high) {
  // Choose rightmost element as pivot
  const pivot = arr[high];
  let i = low - 1;

  // Compare each element with pivot
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  // Place pivot in its final position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}