Linear-Time Sorting Algorithms: Beyond Comparison-Based Sorting

Introduction

Most sorting algorithms we've studied so far—including QuickSort, MergeSort, and HeapSort—are comparison-based, meaning they determine the relative order of elements by comparing them. These algorithms have a proven lower bound of Ω(n log n) comparisons in the worst case.

However, in certain scenarios, we can achieve O(n) time complexity by using algorithms that don't rely on comparing elements directly. These linear-time sorting algorithms leverage specific characteristics of the input data, such as:

• Limited range of values
• Integer or discrete keys
• Uniform distribution

In this article, we'll explore three important linear-time sorting algorithms:

1. Counting Sort: For sorting integers within a small range
2. Radix Sort: For sorting integers with multiple digits/bits
3. Bucket Sort: For sorting uniformly distributed values

Counting Sort

Counting Sort is a non-comparison-based algorithm that works efficiently when the range of input values is not significantly larger than the number of elements to be sorted.

How Counting Sort Works

1. Count the frequency of each distinct element
2. Calculate the position of each element in the sorted output
3. Build the sorted array using these calculated positions

Implementation

function countingSort(arr) {
  if (arr.length <= 1) return [...arr];
  
  // Find minimum and maximum values
  let min = arr[0];
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  
  // Calculate range and create counting array
  const range = max - min + 1;
  const count = new Array(range).fill(0);
  
  // Count occurrences of each element
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  
  // Calculate cumulative count (position of each element)
  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }
  
  // Build the output array
  const output = new Array(arr.length);
  
  // Traverse the input array in reverse to maintain stability
  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i] - min] - 1] = arr[i];
    count[arr[i] - min]--;
  }
  
  return output;
}

Step-by-Step Example

Let's trace through sorting the array [4, 2, 2, 8, 3, 3, 1]:

1. Find min (1) and max (8), so range = 8 - 1 + 1 = 8
2. Create count array of size 8, initialized to zeros: [0, 0, 0, 0, 0, 0, 0, 0]
3. Count occurrences:
   • After counting: [1, 2, 2, 0, 1, 0, 0, 1] (index 0 represents value 1, etc.)
4. Calculate cumulative count:
   • After calculation: [1, 3, 5, 5, 6, 6, 6, 7]
5. Build output array by iterating input in reverse:
   • Start with [4, 2, 2, 8, 3, 3, 1]
   • For 1: place at position count[1-1]-1 = count[0]-1 = 0, decrement count[0]
   • For 3: place at position count[3-1]-1 = count[2]-1 = 4, decrement count[2]
   • And so on...
6. Final sorted array: [1, 2, 2, 3, 3, 4, 8]

Time and Space Complexity

• Time Complexity: O(n + k), where n is the number of elements and k is the range of input
• Space Complexity: O(n + k) for the output and counting arrays

When to Use Counting Sort

Counting Sort is most efficient when:

• The range of input values (k) is not significantly larger than the number of elements (n)
• All values are integers or can be mapped to integers
• Auxiliary space usage is not a concern

Optimized Counting Sort for Objects

We can extend Counting Sort to work with objects by using a key function:

function countingSortObjects(arr, keyFn, min, max) {
  if (arr.length <= 1) return [...arr];
  
  // Use provided min/max or calculate them
  if (min === undefined || max === undefined) {
    min = Infinity;
    max = -Infinity;
    
    for (let i = 0; i < arr.length; i++) {
      const key = keyFn(arr[i]);
      if (key < min) min = key;
      if (key > max) max = key;
    }
  }
  
  const range = max - min + 1;
  const count = new Array(range).fill(0);
  
  // Count occurrences
  for (let i = 0; i < arr.length; i++) {
    count[keyFn(arr[i]) - min]++;
  }
  
  // Calculate cumulative count
  for (let i = 1; i < range; i++) {
    count[i] += count[i - 1];
  }
  
  // Build output array
  const output = new Array(arr.length);
  
  // Traverse input in reverse for stability
  for (let i = arr.length - 1; i >= 0; i--) {
    const key = keyFn(arr[i]);
    output[count[key - min] - 1] = arr[i];
    count[key - min]--;
  }
  
  return output;
}

// Example usage
const students = [
  { name: "Alice", age: 22 },
  { name: "Bob", age: 19 },
  { name: "Charlie", age: 19 },
  { name: "David", age: 21 }
];

const sortedByAge = countingSortObjects(
  students, 
  student => student.age,
  19,  // min age
  22   // max age
);

console.log(sortedByAge);

Radix Sort

Radix Sort extends the idea of Counting Sort to handle larger integers by sorting them digit by digit, from the least significant digit (LSD) to the most significant digit (MSD).

How Radix Sort Works

1. Sort the elements based on the least significant digit using a stable sort
2. Sort the elements based on the next digit
3. Repeat until all digits are processed

Implementation

function radixSort(arr) {
  if (arr.length <= 1) return [...arr];
  
  // Find the maximum number to determine number of digits
  const max = Math.max(...arr);
  
  // Perform counting sort for each digit position
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
  
  return arr;
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  
  // Count occurrences of each digit
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }
  
  // Calculate cumulative count
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  // Build output array
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  
  // Copy output array to arr
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
  }
}

Step-by-Step Example

Let's sort the array [170, 45, 75, 90, 802, 24, 2, 66]:

1. First pass (exp = 1, sort by ones place):

   • Extract digits: [0, 5, 5, 0, 2, 4, 2, 6]
   • After sorting: [170, 90, 802, 2, 24, 45, 75, 66]

2. Second pass (exp = 10, sort by tens place):

   • Extract digits: [7, 9, 0, 0, 0, 2, 7, 6]
   • After sorting: [802, 2, 24, 45, 66, 170, 75, 90]

3. Third pass (exp = 100, sort by hundreds place):

   • Extract digits: [1, 0, 8, 0, 0, 0, 0, 0]
   • After sorting: [2, 24, 45, 66, 75, 90, 170, 802]

Time and Space Complexity

• Time Complexity: O(d × (n + k)), where:
  • n is the number of elements
  • k is the range of input (in this case, 10 for decimal digits)
  • d is the number of digits in the maximum element
• Space Complexity: O(n + k)

For a fixed number of digits, Radix Sort can achieve linear time complexity O(n).

Binary Radix Sort

We can optimize Radix Sort for sorting integers by processing them bit by bit:

function binaryRadixSort(arr) {
  if (arr.length <= 1) return [...arr];
  
  const max = Math.max(...arr);
  let bitMask = 1;
  
  while (bitMask <= max) {
    const zeros = [];
    const ones = [];
    
    // Distribute elements based on the current bit
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] & bitMask) {
        ones.push(arr[i]);
      } else {
        zeros.push(arr[i]);
      }
    }
    
    // Combine results (concatenate zeros and ones)
    arr = [...zeros, ...ones];
    
    // Move to the next bit
    bitMask <<= 1;
  }
  
  return arr;
}

MSD Radix Sort

Most Significant Digit (MSD) Radix Sort processes digits from left to right:

function msdRadixSort(arr) {
  if (arr.length <= 1) return arr;
  
  // Find maximum to determine number of digits
  const max = Math.max(...arr);
  const maxDigits = Math.floor(Math.log10(max)) + 1;
  
  // Start sorting from the most significant digit
  return msdRadixSortRecursive(arr, maxDigits - 1);
}

function msdRadixSortRecursive(arr, digitPosition) {
  if (digitPosition < 0 || arr.length <= 1) return arr;
  
  // Calculate place value (e.g., 100, 10, 1)
  const placeValue = Math.pow(10, digitPosition);
  
  // Distribute elements into buckets (0-9)
  const buckets = Array.from({ length: 10 }, () => []);
  
  for (let i = 0; i < arr.length; i++) {
    const digit = Math.floor(arr[i] / placeValue) % 10;
    buckets[digit].push(arr[i]);
  }
  
  // Recursively sort each bucket by the next digit
  for (let i = 0; i < 10; i++) {
    buckets[i] = msdRadixSortRecursive(buckets[i], digitPosition - 1);
  }
  
  // Concatenate the buckets
  return [].concat(...buckets);
}

Bucket Sort

Bucket Sort distributes elements into a fixed number of buckets, then sorts each bucket individually before concatenating them.

How Bucket Sort Works

1. Create n empty buckets (or a different number based on the distribution)
2. Distribute the elements into buckets based on their values
3. Sort each bucket (using another algorithm or recursively using Bucket Sort)
4. Concatenate all buckets in order

Implementation

function bucketSort(arr, bucketSize = 5) {
  if (arr.length <= 1) return [...arr];
  
  // Find minimum and maximum values
  let min = arr[0];
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }
  
  // Calculate range and number of buckets
  const range = max - min;
  const bucketCount = Math.floor(arr.length / bucketSize) || 1;
  const buckets = Array.from({ length: bucketCount }, () => []);
  
  // Distribute elements into buckets
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.min(
      Math.floor(bucketCount * (arr[i] - min) / (range + 1)),
      bucketCount - 1
    );
    buckets[bucketIndex].push(arr[i]);
  }
  
  // Sort each bucket and concatenate
  const result = [];
  
  for (let i = 0; i < buckets.length; i++) {
    // We can use any sorting algorithm here
    insertionSort(buckets[i]);
    result.push(...buckets[i]);
  }
  
  return result;
}

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = key;
  }
  
  return arr;
}

Step-by-Step Example

Let's sort the array [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51] using Bucket Sort:

1. Create 3 buckets (for this example)
2. Distribute elements:
   • Bucket 0 (0.0-0.33): [0.32, 0.33]
   • Bucket 1 (0.34-0.66): [0.42, 0.52, 0.37, 0.47, 0.51]
   • Bucket 2 (0.67-1.0): []
3. Sort each bucket:
   • Bucket 0: [0.32, 0.33]
   • Bucket 1: [0.37, 0.42, 0.47, 0.51, 0.52]
   • Bucket 2: []
4. Concatenate buckets: [0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52]

Time and Space Complexity

• Time Complexity:
  • Average case: O(n + n²/k + k), where k is the number of buckets
  • With k ≈ n, we get O(n) average time
  • Worst case (all elements in one bucket): O(n²)
• Space Complexity: O(n + k) for the buckets

When to Use Bucket Sort

Bucket Sort works best when:

• Input is uniformly distributed over a range
• Elements can be mapped to buckets easily
• Each bucket is expected to have few elements

Optimized Bucket Sort for Floating-Point Numbers

Here's a specialized version for sorting floating-point numbers in the range [0, 1):

function floatBucketSort(arr) {
  if (arr.length <= 1) return [...arr];
  
  const n = arr.length;
  const buckets = Array.from({ length: n }, () => []);
  
  // Distribute elements into n buckets
  for (let i = 0; i < n; i++) {
    const bucketIndex = Math.floor(n * arr[i]);
    buckets[bucketIndex].push(arr[i]);
  }
  
  // Sort each bucket and concatenate
  const result = [];
  
  for (let i = 0; i < n; i++) {
    // For small buckets, insertion sort is efficient
    insertionSort(buckets[i]);
    result.push(...buckets[i]);
  }
  
  return result;
}

Comparing Linear-Time Sorting Algorithms

Counting Sort vs. Radix Sort vs. Bucket Sort

Algorithm	Time Complexity	Space Complexity	Best For	Limitations
Counting Sort	O(n + k)	O(n + k)	Small range integers	Large range makes it inefficient
Radix Sort	O(d(n + k))	O(n + k)	Large integers, strings	Requires stable sort for digits
Bucket Sort	O(n) average, O(n²) worst	O(n + k)	Uniformly distributed data	Poor distribution leads to O(n²)

When to Choose Each Algorithm

• Counting Sort: When sorting integers with a small range relative to n
• Radix Sort: When sorting integers or strings with many digits/characters
• Bucket Sort: When data is approximately uniformly distributed

Practical Applications

1. Sorting Event Logs by Timestamp

Radix Sort can efficiently sort event logs by timestamp:

function sortEventsByTimestamp(events) {
  // Extract timestamps (assume they're integers representing milliseconds)
  const timestamps = events.map(event => event.timestamp);
  
  // Find range for counting sort
  const minTimestamp = Math.min(...timestamps);
  const maxTimestamp = Math.max(...timestamps);
  
  if (maxTimestamp - minTimestamp > 1000000) {
    // Large range: use radix sort
    return radixSortEvents(events);
  } else {
    // Small range: use counting sort
    return countingSortObjects(
      events,
      event => event.timestamp,
      minTimestamp,
      maxTimestamp
    );
  }
}

function radixSortEvents(events) {
  if (events.length <= 1) return [...events];
  
  const max = Math.max(...events.map(event => event.timestamp));
  
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortEventsByDigit(events, exp);
  }
  
  return events;
}

function countingSortEventsByDigit(events, exp) {
  const n = events.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(events[i].timestamp / exp) % 10;
    count[digit]++;
  }
  
  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }
  
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(events[i].timestamp / exp) % 10;
    output[count[digit] - 1] = events[i];
    count[digit]--;
  }
  
  for (let i = 0; i < n; i++) {
    events[i] = output[i];
  }
}

2. IP Address Sorting

Bucket Sort can efficiently sort IP addresses:

function sortIPAddresses(ips) {
  // Convert IPs to numeric representation
  const ipObjects = ips.map(ip => ({
    original: ip,
    numeric: ipToNumeric(ip)
  }));
  
  // Sort using bucket sort
  const sorted = bucketSort(ipObjects, 256);
  
  // Return original string IPs
  return sorted.map(obj => obj.original);
}

function ipToNumeric(ip) {
  const parts = ip.split('.');
  return parts.reduce((sum, part, index) => {
    return sum + parseInt(part) * Math.pow(256, 3 - index);
  }, 0);
}

// Modify bucket sort to work with objects
function bucketSort(arr, bucketSize) {
  // Implementation adjusted for IP objects
  // ...
}

3. Sorting Students by Grade Ranges

Counting Sort efficiently sorts students by grade ranges:

function sortStudentsByGrade(students) {
  // Grades typically range from 0-100
  return countingSortObjects(
    students,
    student => student.grade,
    0,
    100
  );
}

// Example usage
const students = [
  { name: "Alice", grade: 92 },
  { name: "Bob", grade: 78 },
  { name: "Charlie", grade: 85 },
  { name: "David", grade: 92 }
];

const sortedStudents = sortStudentsByGrade(students);
console.log(sortedStudents);

Hybrid Approaches

For real-world scenarios, hybrid approaches often provide the best performance:

function hybridSort(arr) {
  // Choose algorithm based on array characteristics
  
  if (arr.length <= 10) {
    return insertionSort(arr);
  }
  
  // Check if array elements are integers within a small range
  const isInteger = arr.every(x => Number.isInteger(x));
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  
  if (isInteger && range <= 5 * arr.length) {
    return countingSort(arr);
  }
  
  if (isInteger) {
    return radixSort(arr);
  }
  
  // Check if values are uniformly distributed
  const isUniform = checkUniformDistribution(arr);
  if (isUniform) {
    return bucketSort(arr);
  }
  
  // Default to a general-purpose algorithm
  return arr.sort((a, b) => a - b); // JavaScript's native sort
}

function checkUniformDistribution(arr) {
  // Simplified check - could be more sophisticated
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  
  // Create 10 buckets and count elements in each
  const bucketSize = (max - min) / 10;
  const bucketCounts = new Array(10).fill(0);
  
  for (let i = 0; i < arr.length; i++) {
    const bucketIndex = Math.min(
      Math.floor((arr[i] - min) / bucketSize),
      9
    );
    bucketCounts[bucketIndex]++;
  }
  
  // Calculate standard deviation of bucket counts
  const mean = arr.length / 10;
  const variance = bucketCounts.reduce(
    (sum, count) => sum + Math.pow(count - mean, 2),
    0
  ) / 10;
  const stdDev = Math.sqrt(variance);
  
  // If standard deviation is low, distribution is relatively uniform
  return stdDev < mean / 2;
}

Advanced Topics

1. String Sorting with MSD Radix Sort

function msdRadixSortStrings(arr) {
  if (arr.length <= 1) return arr;
  
  // Find the maximum string length
  const maxLength = Math.max(...arr.map(str => str.length));
  
  // Start sorting from the first character position
  return msdRadixSortStringsHelper(arr, 0, maxLength);
}

function msdRadixSortStringsHelper(arr, charPos, maxLength) {
  if (charPos >= maxLength || arr.length <= 1) return arr;
  
  // Create buckets for each possible character (ASCII)
  const buckets = Array.from({ length: 257 }, () => []);
  
  // Distribute elements into buckets
  for (let i = 0; i < arr.length; i++) {
    // If we're past the end of this string, put it in bucket 0
    const charCode = charPos < arr[i].length 
      ? arr[i].charCodeAt(charPos) + 1 // +1 to leave bucket 0 for empty slots
      : 0;
    buckets[charCode].push(arr[i]);
  }
  
  // Recursively sort each non-empty bucket by the next character
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i].length > 1) {
      buckets[i] = msdRadixSortStringsHelper(buckets[i], charPos + 1, maxLength);
    }
  }
  
  // Concatenate the buckets
  return [].concat(...buckets);
}

2. In-Place Counting Sort

function inPlaceCountingSort(arr) {
  if (arr.length <= 1) return arr;
  
  // Find range
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const range = max - min + 1;
  
  // Count frequencies
  const count = new Array(range).fill(0);
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  
  // Modify input array in-place
  let index = 0;
  for (let i = 0; i < range; i++) {
    while (count[i] > 0) {
      arr[index++] = i + min;
      count[i]--;
    }
  }
  
  return arr;
}

3. Multi-Key Bucket Sort

For sorting objects by multiple criteria:

function multiKeyBucketSort(arr, keyFunctions) {
  if (arr.length <= 1 || keyFunctions.length === 0) return [...arr];
  
  // Get the first key function
  const keyFn = keyFunctions[0];
  const remainingKeyFns = keyFunctions.slice(1);
  
  // Create buckets
  const buckets = {};
  
  // Distribute elements by the current key
  for (let i = 0; i < arr.length; i++) {
    const key = keyFn(arr[i]);
    
    if (!buckets[key]) {
      buckets[key] = [];
    }
    
    buckets[key].push(arr[i]);
  }
  
  // Sort each bucket by remaining keys
  const sortedKeys = Object.keys(buckets).sort();
  const result = [];
  
  for (const key of sortedKeys) {
    if (remainingKeyFns.length > 0) {
      // Recursively sort by remaining keys
      result.push(...multiKeyBucketSort(buckets[key], remainingKeyFns));
    } else {
      // No more keys, just add elements
      result.push(...buckets[key]);
    }
  }
  
  return result;
}

// Example usage: Sort students by grade then name
const studentsSortedByGradeAndName = multiKeyBucketSort(
  students,
  [
    student => student.grade, // Primary key: grade
    student => student.name   // Secondary key: name
  ]
);

Conclusion

Linear-time sorting algorithms provide an efficient alternative to comparison-based sorting when we can leverage specific properties of the input data. By breaking free from the Ω(n log n) lower bound of comparison sorts, these algorithms can achieve O(n) time complexity in many practical scenarios.

The key insights from these algorithms extend beyond sorting:

1. Domain-specific optimizations often outperform general-purpose algorithms
2. Understanding data characteristics leads to more efficient algorithm selection
3. Hybrid approaches combine strengths of different algorithms for real-world scenarios

When implementing a sorting algorithm, consider not just the asymptotic complexity but also:

• The expected distribution of input data
• Memory constraints
• Stability requirements
• Whether the algorithm needs to be adaptive to partially sorted inputs

In practice, modern programming languages typically implement hybrid sorting algorithms that automatically adapt to different input characteristics. Understanding these linear-time sorting algorithms provides insight into how these optimizations work and when to apply specialized sorting techniques to your own problems.

In our next article, we'll explore advanced sorting techniques and specialized algorithms for external sorting, parallel sorting, and sorting in distributed systems.