My Favorite Linear-time Sorting Algorithm

By Franziska Hinkelmann

Counting sort with a twist

The problem: Given an unsorted array of numbers, find the maximum difference between the successive elements in its sorted form. The numbers can be negative or decimals.

Given [21, 41, 17, 45, 9, 28], the maximum difference is 13.

Straightforward Algorithm

const maxGap = input =>  input    .sort((a, b) => a — b)    .reduce((acc, cur, idx…