Sorting in Linear time

1. Counting Sort (input consists of integers in a small range)
2. Radix Sort
3. Bucket Sort (input is uniformly distributed)

Any comparison sort algorithm requires nlgn comparisons in the worse case.

Counting Sort (Running time: theta(n))

Counting sort assume that each of the n input elements is an integer in the range 0 to k, for some integer k. The basic idea of counting sort is to determine, for each input element x, the number of elements less than x. This information can be used to place element x directly into its position in the output array. We need to do a slight modification to handle the situation in which several elements have the same value. In practice, we usually use counting sort when we have k = O(n), the running time is theta(n).

Counting sort is stable: numbers with the same value appear in the output array in the same order as they do in the input array, which is very important since counting sort is often used as a subroutine in radix sort.

Counting sort requires two other arrays: the array B[1...n] holds the sorted output, and the array C[0...k] provides temporary working storage.

The algorithm itself is not complicated, watch out boundary errors when you try to implement it.

Radix Sort

Radix-Sort(A, d)
1. for i <-- 1 to d
2. do use a stable sort to sort array A on digit i

Radix sort can be used to sort records of information that are keyed by multiple fields.

Given n d-digit numbers in which each digit can take on up to k possible values, Radix-Sort correctly sorts these numbers in theta(d(n+k)) time. When d is constant and k = O(n), radix sort runs in linear time.

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Bucket sort is a generalization of pigeonhole sort.