Sorting in linear time

Sorting in linear time

Counting sort

conditions:

1. each of the n input elements is an integer in the range between 0 to k

2. k is some integer that: k=O(n)

method:

1. determine, for each input element x, the number of elements less than x

2. place element x directly into its position in the output array

Notes: counting sort is stable

Radix sort

conditions:

1. each of the n input elements has d digits, each digit is in the range between 0 to k

2. d is constant, and k=O(n)

method:

from the lowest to highest order digit, use a stable sort (e.g. counting sort) to sort the array on that digit

examples:

1. sort dates by three keys: year, month, and day

2. sort n integers in the range 0 to n^2-1 in O(n) time (convert the input integers into n-based digits). Similarly, it can be extended to the range 0 to n^k-1, where k is a constant.

Bucket sort

conditions:

1. the input is generated by a random process that distributes elements uniformly

2. the input elements are real numbers in the range of [0,1)

method:

1. divide the elements into one of the n equal-sized buckets, so that A[i] is in the bucket indexed by floor(n*A[i])

2. sort elements in each bucket using some comparison sort (e.g. insertion sort)

3. concatenate the buckets from 1 to n together in order