Linear-time sorting, part 2: Counting Sort, Radix Sort and Bucket Sort
Three linear-time sorting algorithms: counting sort works well if the numbers to be sorted are not too big (O(n)). With Radix Sort we can push things a bit further. Finally, Bucket Sort is not for sorting integers, but numbers nicely spread out between 0 and 1.
Timeline:
0:00 Counting Sort: position(i)
5:06 Counting Sort: algorithm
11:27 Counting Sort: correctness + running time
18:14 Radix Sort
27:42 Bucket Sort
33:58 Bucket Sort: running time
38:22 E[n_i^2]
43:28 Wrap-Up