linsort - 23
Lin / Devi
Relies on no bucket getting too many values.
All lines except insertion sorting in line 5 take O(n) altogether.
Intuitively, if each bucket gets a constant number of elements, it takes O(1) time to sort each bucket O(n) sort time for all buckets.
We “expect” each bucket to have few elements, since the average is 1 element per bucket.
But we need to do a careful analysis.