Linear time sorting

Sorting arrays in linear time is possible, but it can only be done with certain restrictions (our array has to meet some desired properties).

Problem

Input: array $A[\mathrm{1..}n]$ of integers in between $[\mathrm{1..}R]$. That is, the integers in this array are within a certain range $R$.

Output: a sorted version of $A$.

Count sort

1. Given our array $A$ and a range $\mathrm{1..}R$, we create a new array $C[\mathrm{1..}R]$. For each element in $A[i]$, we use the value to index into $C$, and increment by one. That is, $C[A[i]]=C[A[i]]+1$.
2. We then iterate through $C$, and for each index and frequency, we duplicate that value by the frequency inside a new array $B$. When done, this would have all the elements of $A$ in sorted order.

Runtime analysis

$O(R)$ to initialize $C$ to all zeroes, $O(n)$ to iterate through $A$ and map elements to frequencies, and then $O(R)$ to iterate through $C$ to populate $B$ and duplicate elements as needed.

Total runtime is therefore $O(n+R)$. When $R\le O(n)$, this algorithm is linear time.

Radix sort

We begin with count sort.

1. Instead of an array $C$ of numbers, we make $C$ an array of linked lists. Each linked list stored an instance of the number, and we store an additional piece of info with it, that is the index of where it is in $A$. This allows us to remember the order in which elements were inserted into $C$.
2. We represent each $A[i]\in A$ in a base $k$ representation. This means that it will take a max of ${\log }_{k}R$ digits to represent every possible number in $A$ in base $k$.
3. Beginning with the least significant digit, we use count sort to sort the columns. when we get to the most significant digit, we will have a sorted array. For some fucking reason

Runtime analysis

Count sort takes $O(n+k)$, and there are ${\log }_{k}R$ columns/digits, so runtime is $O(n+k)\cdot O({\log }_{k}R)$.

Using logarithm rules, we get $O(n+k)\cdot O\left(\frac{\log R}{\log k}\right)$. Choosing $k=n$ simplifies this to

$$O(n)\cdot O\left(\frac{\log R}{\log n}\right)$$

For values $R\le n$, this simplifies down to $O(n)\cdot O(1)=O(n)$.