Quick Sort

Quick Sort is a highly efficient divide-and-conquer 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 repeated recursively.

Complexity Analysis

Best Case

O(n log n)

Average Case

O(n log n)

Worst Case

O(n²)

Space Complexity

O(log n)

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 left subarray
        quickSort(arr, low, pivotIndex - 1);

        // Recursively sort right subarray
        quickSort(arr, pivotIndex + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    const pivot = arr[high];
    let i = low - 1;

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

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

How Quick Sort Works

Quick Sort uses a divide-and-conquer strategy with a partitioning step that rearranges the array so that all elements smaller than a chosen pivot are on the left, and all elements larger are on the right.

Algorithm Steps:

  1. Choose Pivot: Select an element as the pivot (commonly the last element)
  2. Partition: Rearrange array so elements ≤ pivot are left, elements > pivot are right
  3. Recursive Sort Left: Apply quicksort to the left subarray
  4. Recursive Sort Right: Apply quicksort to the right subarray
  5. Base Case: Subarrays of size 1 or 0 are already sorted

Pivot Selection Strategies:

  • Last Element: Simple but can lead to worst case
  • Random Pivot: Better average performance
  • Median of Three: More sophisticated selection
  • First Element: Simple but potentially problematic

Key Characteristics:

  • In-place: Requires only O(log n) additional space
  • Unstable: Does not maintain relative order of equal elements
  • Cache-friendly: Good memory access patterns
  • Tail recursive: Can be optimized to use less stack space

Real-World Usage:

  • C++ STL sort: Introsort (hybrid of quicksort and heapsort)
  • Python's sort: Timsort (hybrid with insertion sort)
  • Arrays.sort() in Java: Dual-pivot quicksort variant
  • Most programming languages: Default sorting algorithm

Performance Insights:

  • Best Case: O(n log n) with good pivot selection
  • Worst Case: O(n²) with poor pivot selection (already sorted)
  • Average Case: O(n log n) with random pivot selection
  • Constant Factors: Often fastest in practice due to cache efficiency