Quick Sort

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a ‘pivot’ element and partitioning the array around it.

Key Concepts

• Divide: Select a pivot and partition the array
• Conquer: Recursively sort the subarrays
• Combine: No combining needed - elements are sorted in place

Interactive Visualization

1function quickSort(arr, low, high) {
2  if (low < high) {
3    // Select pivot (last element)
4    const pivot = arr[high];
5    let i = low - 1;
6 
7    // Partition
8    for (let j = low; j < high; j++) {
9      if (arr[j] < pivot) {
10        i++;
11        [arr[i], arr[j]] = [arr[j], arr[i]];
12      }
13    }
14    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
15    const pi = i + 1;
16 
17    quickSort(arr, low, pi - 1);
18    quickSort(arr, pi + 1, high);
19  }
20}

How It Works

1. Choose a pivot - Select an element as the pivot (we use the last element)
2. Partition - Rearrange elements so smaller ones are left of pivot, larger ones are right
3. Recurse - Apply the same process to left and right subarrays

Complexity Analysis

Space Complexity: O(log n) for the recursive call stack

When to Use Quick Sort

• General-purpose sorting when average-case performance matters
• When in-place sorting is required (minimal extra memory)
• Large datasets where O(n log n) average performance is acceptable

When to Avoid

• Already sorted or nearly sorted arrays (worst case O(n²))
• When stability is required (Quick Sort is not stable)
• Small datasets (insertion sort may be faster due to lower overhead)