Speed:

Quick Sort

Average: O(n log n)Worst: O(n²)Space: O(log n)

⚡How Quick Sort Works

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.

The algorithm follows these key steps:

Choose Pivot: Select an element as the pivot (often the last element)
Partition: Rearrange array so elements < pivot are before it, elements > pivot are after
Recursion: Apply quick sort to the sub-arrays on both sides of the pivot
Base Case: Single elements or empty arrays are already sorted

💻Implementation

// Quick Sort Implementation
function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Partition the array and get pivot index
    let pivotIndex = partition(arr, low, high);
    
    // Recursively sort elements before and after partition
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  // Choose the rightmost element as pivot
  let pivot = arr[high];
  let i = low - 1; // Index of smaller element
  
  for (let j = low; j < high; j++) {
    // If current element is smaller than or equal to pivot
    if (arr[j] <= pivot) {
      i++;
      [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;
}

// Alternative with random pivot
function quickSortRandomized(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    // Randomize pivot to avoid worst case
    let randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    
    let pivotIndex = partition(arr, low, high);
    quickSortRandomized(arr, low, pivotIndex - 1);
    quickSortRandomized(arr, pivotIndex + 1, high);
  }
  return arr;
}

📊Performance Analysis

Time Complexity

• Best: O(n log n) - balanced partitions
• Average: O(n log n)
• Worst: O(n²) - already sorted with bad pivot
• Recurrence: T(n) = T(k) + T(n-k-1) + O(n)

Space & Properties

• Space: O(log n) recursion stack
• Not stable: relative order not preserved
• In-place: sorts within original array
• Cache-friendly: good locality of reference

🎯 Pivot Selection Strategies

• First/Last element: Simple but can be O(n²)
• Random pivot: Avoids worst case on sorted data
• Median-of-three: Better performance, less variance
• Median-of-medians: Guarantees O(n log n) but complex

🚀 Why Quick Sort is Popular

• Fast in practice: Low constant factors
• Cache efficient: Good memory access patterns
• In-place sorting: Minimal extra memory
• Widely implemented: Standard library choice