Specialized Sorting (O(n))

Is it mathematically possible to sort an array faster than $O(N \log N)$? Yes, but only under specific constraints.

If we are sorting arbitrary data (where we have to compare elements using <, >, or ==), it is mathematically proven that $O(N \log N)$ is the absolute lower bound. However, if we know something specific about the data (e.g., "They are all integers between 1 and 100"), we can bypass mathematical comparisons entirely and use integer counting to sort in $O(N)$ linear time!

1. Counting Sort

Counting Sort works by counting the occurrences of each unique integer in the input array. It uses these counts to mathematically calculate the exact index each integer belongs to in the sorted output array.

Constraints: The integers must be in a small, known range (e.g., 0 to K).

• Time Complexity: $O(N + K)$ (where K is the range of inputs).
• Space Complexity: $O(K)$ (An array of size K is needed to store the counts).

When to use it

If you are sorting an array of 1 million student test scores (which range from 0 to 100). $O(N \log N)$ is too slow. Because $K = 100$, Counting Sort will sort 1 million items in near-instant $O(N)$ time.

Implementation

function countingSort(arr: number[], maxVal: number): number[] {
  // 1. Create a count array of size maxVal + 1
  const count = new Array(maxVal + 1).fill(0);
  
  // 2. Count occurrences of each number
  for (const num of arr) {
    count[num]++;
  }
  
  // 3. Reconstruct the sorted array directly from the counts
  const result: number[] = [];
  for (let i = 0; i <= maxVal; i++) {
    while (count[i] > 0) {
      result.push(i);
      count[i]--;
    }
  }
  
  return result;
}

// usage: countingSort([4, 2, 2, 8, 3, 3, 1], 8)

2. Radix Sort

Counting Sort fails if the range is massive (e.g., sorting 10 numbers where one is 9,999,999,999—creating a count array of 10 billion items will crash your RAM).

Radix Sort solves this. It sorts the numbers digit by digit, starting from the least significant digit (ones place) to the most significant digit. It uses a stable sub-sort algorithm (usually a modified Counting Sort) to sort the specific digits.

• Time Complexity: $O(d \cdot (N + b))$, where $d$ is the number of digits, and $b$ is the base (10 for decimal).
• Space Complexity: $O(N + b)$

3. Bucket Sort

Bucket Sort divides the range of values into a set of "buckets". Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying Bucket Sort.

Constraints: Works best when the input is uniformly distributed across a range (e.g., floating-point numbers from 0.0 to 1.0).

• Time Complexity: $O(N + K)$ (Average), $O(N^2)$ (Worst case if all elements fall into a single bucket and insertion sort is used).
• Space Complexity: $O(N + K)$