Speed:

Count Sort

Time: O(n + k)Space: O(k)Stable

📊How Count Sort Works

Count Sort is a non-comparison based sorting algorithm that counts the occurrences of each distinct element in the array. It works by determining the range of input data and counting how many times each value appears.

The algorithm is particularly efficient when the range of input data (k) is not significantly larger than the number of elements (n). The steps are:

Find the maximum element to determine the range.
Create a count array to store frequencies.
Count occurrences of each element.
Reconstruct the sorted array using the count information.

💻Implementation

// Count Sort (for non-negative integers)
function countSort(arr) {
  if (arr.length === 0) return arr;
  
  // Find the maximum element
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  
  // Count occurrences of each element
  for (let i = 0; i < arr.length; i++) {
    count[arr[i]]++;
  }
  
  // Reconstruct the sorted array
  const result = [];
  for (let i = 0; i <= max; i++) {
    while (count[i] > 0) {
      result.push(i);
      count[i]--;
    }
  }
  return result;
}

🔍Algorithm Analysis

Time Complexity

• Best: O(n + k)
• Average: O(n + k)
• Worst: O(n + k)
• where k is the range of input

Key Properties

• Non-comparison based algorithm
• Stable sorting (maintains relative order)
• Works only with non-negative integers
• Efficient when k is not much larger than n

🎯 Best Use Cases

• Small range of integers
• Frequency counting problems
• As subroutine in radix sort
• When stability is required

⚠️ Limitations

• Only works with non-negative integers
• Space complexity increases with range
• Inefficient when range is much larger than n
• Cannot handle floating-point numbers directly