Speed:

Heap Sort

Time: O(n log n)Space: O(1)Not Stable

🏔️How Heap Sort Works

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap from the input data, then repeatedly extracting the maximum element and placing it at the end of the sorted portion.

The algorithm consists of two main phases:

Heapify: Build a max heap from the unsorted array
Extract-Max: Repeatedly remove the root (max element) and restore heap property
The extracted elements form the sorted array in descending order
Since we want ascending order, we place elements at the end of the array

💻Implementation

// Heap Sort Implementation
function heapSort(arr) {
  const n = arr.length;
  
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root to end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    
    // Call heapify on the reduced heap
    heapify(arr, i, 0);
  }
  return arr;
}

function heapify(arr, n, i) {
  let largest = i; // Initialize largest as root
  let left = 2 * i + 1; // left child
  let right = 2 * i + 2; // right child
  
  // If left child is larger than root
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  // If right child is larger than largest so far
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  // If largest is not root
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest); // Recursively heapify
  }
}

🔍Heap Properties & Analysis

Heap Structure

• Complete binary tree
• Parent at index i, children at 2i+1 and 2i+2
• Max heap: parent ≥ children
• Height: O(log n)

Complexity Analysis

• Build heap: O(n)
• Extract max: O(log n)
• Total: O(n log n)
• Space: O(1) in-place

✅ Advantages

• Guaranteed O(n log n) worst-case
• In-place sorting (O(1) space)
• Consistent performance across all inputs
• Good cache performance

❌ Disadvantages

• Not stable (doesn't preserve order)
• Slower than quicksort in average case
• Complex implementation
• Poor performance on small arrays