This tutorial is about two awesome, non-comparison-based sorting algorithms. While many sorting algorithms require a comparator function that compares two values at a time, these two and their family of non-comparison methods rely on other techniques instead. We'll cover counting sort and radix sort, which are both very efficient. Bucket sort is another one, but it's a close enough cousin of radix sort that we'll point to other references for more information on it.

Before going into details, we must keep in mind that any sorting algorithm has to scan the unsorted array at least once. This provides us the following important rule:

Any sorting algorithm will take at least O(n) time

This statement constrains the best possible shortest sorting time - we cannot sort an array in a time complexity less than O(n). Of course, there are sorting algorithms which take up significantly more time. Given this ambitious target of O(n), let's look at how counting sort and radix sort stack up.

Here's a preview of the final implementations, but we'll be sure to walk you through the theory before revealing them again!

xxxxxxxxxx

console.log(countingSort([5, 0, 65, 4, 10]));

function countingSort(arr) {

  let counts = [];

  let n = 0;

  let max = Math.max(...arr);

​

  // Set up keys

  for (let i = 0; i <= max; i++) {

    counts[i] = 0;

  }

​

  // Count

  for (let i = 0; i < arr.length; i++) {

    counts[arr[i]]++;

  }

​

  // Order by count

  for (let i = 0; i <= max; i++) {

    for (let j = 0; j < counts[i]; j++) {

      arr[n] = i;

      n++;

    }

  }

​

  return arr;

}

​

function getDigit(num, i) {

  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;

}