Quick Sort

A divide-and-conquer algorithm that picks a pivot element and partitions the array around it, then recursively sorts the sub-arrays.

Algorithm Information

Time Complexity

Best: O(n log n)

Average: O(n log n)

Worst: O(n²)

Space Complexity

O(log n)

Properties

• Divide-and-conquer algorithm

• In-place sorting

• Not stable (may change relative order)

• Recursive implementation

1/50

Speed: 1x

Algorithm Code

1function quickSort(arr, low = 0, high = arr.length - 1) {
2  if (low < high) {
3    // Partition the array and get pivot index
4    const pivotIndex = partition(arr, low, high);
5    
6    // Recursively sort elements before and after partition
7    quickSort(arr, low, pivotIndex - 1);
8    quickSort(arr, pivotIndex + 1, high);
9  }
10  return arr;
11}
12 
13function partition(arr, low, high) {
14  // Choose rightmost element as pivot
15  const pivot = arr[high];
16  let i = low - 1; // Index of smaller element
17  
18  for (let j = low; j < high; j++) {
19    // If current element is smaller than or equal to pivot
20    if (arr[j] <= pivot) {
21      i++;
22      [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
23    }
24  }
25  
26  // Place pivot in correct position
27  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
28  return i + 1; // Return pivot index
29}

Variable State

low:0

high:6

pivot:90

i:-1

j:0

pivotIndex:6

Call Stack

quickSort(0, 6)

Array Visualization

Watch how Quick Sort partitions the array around pivot elements and recursively sorts sub-arrays

640

341

252

123

224

115

906

Statistics

Comparisons0

Swaps0

Step1 / 50

Legend

Comparing with Pivot

Swapping Elements

Sorted (Final Position)

Unsorted

Starting Quick Sort algorithm

How Quick Sort Works

Discover the power of partitioning in this efficient divide-and-conquer algorithm with average O(n log n) performance.

Algorithm Overview

Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a 'pivot' element and partitioning the array around it. Elements smaller than the pivot go to the left, larger elements go to the right, then the process is recursively applied to the subarrays.

🎯 Partitioning Strategy

The key insight is the partition operation: after partitioning around a pivot, the pivot is in its final sorted position, and we never need to move it again. This creates two independent subproblems that can be solved recursively, leading to excellent average-case performance.

Step-by-Step Process

Choose Pivot

Select a pivot element from the array. Common strategies include choosing the first, last, middle, or a random element. The choice affects performance but not correctness.

const pivot = arr[high];

Partition Array

Rearrange the array so all elements smaller than the pivot come before it, and all elements greater come after it. The pivot is now in its final position.

let i = low - 1;
for (let j = low; j < high; j++) {
  if (arr[j] < pivot) {
    swap(arr[++i], arr[j]);
  }
}

Place Pivot

Swap the pivot with the element at the partition boundary. The pivot is now in its correct final position in the sorted array.

Key Insight: After partitioning, the pivot never needs to move again!

Recursive Calls

Recursively apply quick sort to the left subarray (elements smaller than pivot) and right subarray (elements larger than pivot).

quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);

Partitioning in Action

Here's how the partition operation works with an example:

Initial: [3, 6, 8, 10, 1, 2, 1] (pivot = 1, last element)

Step 1: [3, 6, 8, 10, 1, 2, 1] - i = -1

Step 2: [3, 6, 8, 10, 1, 2, 1] - 1 < 1? No, i stays -1

Step 3: [3, 6, 8, 10, 1, 2, 1] - 2 < 1? No, i stays -1

Final: [1, 6, 8, 10, 1, 2, 3] - Swap pivot with arr[i+1]

Pivot 1 is now in position 0, with no smaller elements to its left

🔄 Partition Invariant

During partitioning, we maintain the invariant: elements at indices [low...i] are ≤ pivot, elements at indices [i+1...j-1] are > pivot, and elements at indices [j...high-1] are unprocessed.

Complete Implementation

Here's the complete quick sort implementation with Lomuto partition scheme:

function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        // Partition the array and get pivot index
        const pivotIndex = partition(arr, low, high);
        
        // Recursively sort elements before and after partition
        quickSort(arr, low, pivotIndex - 1);    // Left subarray
        quickSort(arr, pivotIndex + 1, high);   // Right subarray
    }
}

function partition(arr, low, high) {
    // Choose the rightmost element as pivot
    const pivot = arr[high];
    
    // Index of smaller element (indicates right position of pivot)
    let i = low - 1;
    
    for (let j = low; j < high; j++) {
        // If current element is smaller than or equal to pivot
        if (arr[j] <= pivot) {
            i++; // Increment index of smaller element
            [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap elements
        }
    }
    
    // Place pivot in correct position
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    
    return i + 1; // Return position of pivot
}

// Alternative: Hoare Partition Scheme (more efficient)
function hoarePartition(arr, low, high) {
    const pivot = arr[low]; // Choose first element as pivot
    let i = low - 1;
    let j = high + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

// Example usage:
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("Original:", numbers);
quickSort(numbers);
console.log("Sorted:", numbers);

Key Concepts & Characteristics

✅ Advantages

•Fast average case: O(n log n) on average, often faster than merge sort
•In-place sorting: Only requires O(log n) extra space for recursion
•Cache-friendly: Good spatial locality of reference
•Practical performance: Low constant factors make it very fast
•Tail recursion: Can be optimized to reduce stack usage

❌ Disadvantages

•Worst-case O(n²): Poor pivot choices lead to quadratic time
•Unstable: Equal elements may change relative order
•Sensitive to input: Performance depends on pivot selection
•Not adaptive: Doesn't benefit from partially sorted data
•Deep recursion: Can cause stack overflow on worst-case input

⚠️ Worst-Case Scenario

Quick sort's worst case occurs when the pivot is always the smallest or largest element, creating highly unbalanced partitions. This happens with already sorted arrays when using first/last element as pivot, leading to O(n²) time complexity and O(n) space complexity.

Complexity Analysis

Best Case

O(n log n)

Pivot always divides array into two equal halves, creating balanced recursion tree.

Average Case

O(n log n)

Random pivot selection leads to reasonably balanced partitions on average.

Worst Case

O(n²)

Pivot is always minimum or maximum, creating unbalanced partitions.

Mathematical Analysis

Best/Average Case: T(n) = 2T(n/2) + O(n) = O(n log n)

Worst Case: T(n) = T(n-1) + T(0) + O(n) = O(n²)

Expected Depth: O(log n) for random pivots

Partition Cost: O(n) for each level

Space Complexity: O(log n) - Recursion stack depth

Pivot Selection Strategies

Common Strategies

•
First Element: Simple but poor for sorted data
Time: O(1), Risk: High for sorted input
•
Last Element: Most common, same issues as first
Time: O(1), Risk: High for sorted input
•
Random Element: Good average performance
Time: O(1), Risk: Low, probabilistic guarantee
•
Median-of-Three: Choose median of first, middle, last
Time: O(1), Risk: Lower, better practical performance

Advanced Techniques

•
Median-of-Medians: Guaranteed good pivot
Time: O(n), Guarantee: Worst-case O(n log n)
•
Introsort: Switch to heapsort if recursion too deep
Used in C++ std::sort, guarantees O(n log n)
•
Dual-Pivot: Use two pivots for 3-way partitioning
Used in Java's Arrays.sort(), better for duplicates

When to Use Quick Sort

✅ Excellent for:

• General-purpose sorting: Great all-around performance
• Large datasets: Excellent average-case performance
• Memory-constrained systems: In-place with low space overhead
• Cache-sensitive applications: Good spatial locality
• Random data: Performs very well on random inputs
• Systems programming: Used in many standard libraries

❌ Consider alternatives for:

• Guaranteed performance: Use merge sort or heap sort
• Stable sorting required: Use merge sort or stable variants
• Nearly sorted data: Use insertion sort or adaptive algorithms
• Adversarial input: Risk of worst-case O(n²) performance
• Small datasets: Insertion sort may be faster

🏆 Industry Standard

Quick sort (with optimizations) is used in C's qsort(), C++'s std::sort(Introsort), and Java's Arrays.sort() for primitive types. Its combination of excellent average performance, in-place operation, and cache efficiency makes it the go-to choice for most sorting needs.

Common Optimizations

Performance Optimizations

• Insertion sort for small subarrays: Switch when size < 10-20
• Tail recursion elimination: Reduce stack usage
• Iterative implementation: Avoid recursion overhead
• Three-way partitioning: Handle many duplicate keys efficiently

Robustness Improvements

• Randomized pivot: Avoid worst-case on sorted input
• Median-of-three: Better pivot selection
• Introsort hybrid: Fall back to heap sort if too deep
• Dual-pivot quicksort: Better performance on modern hardware

💡 Pro Tip: Hybrid Approach

Modern implementations often combine multiple techniques: use quicksort for large subarrays, insertion sort for small ones, and heap sort as a fallback for deep recursion. This gives you the best of all worlds: fast average case, good worst case, and excellent small-array performance.