Other sort aglogos

bucketsort idea

1. Divide interval [a, b) into B (equally sized) subintervals (’Buckets’)

2. Sort the numbers in each subinterval separately (e.g., with MergeSort)

3. concatenate subseq

Bucket assignment

can be implemented as an array with a list in each entry

worst case: all in 1 bucket

best case: evenly sorted

Counting sort algo

1. Create array C of length k.

2. For each number in the input ai, set C[ai] to C[ai] + 1 (’Counting’).

3. Traverse C from left to right and write out the values with corresponding

frequency.

counting sort issue and solution

Prob: Values were keys of complex objects

cummulative freq

Radixsort idea

Similar to CountingSort, but digit-wise from back to front(LSD)

d-ary digits with s places

Radixsort algo

Sort by last digit with CountingSort (with k=d)

i. Sort by (s+1-i)th digit with CountingSort (with k=d)

inc d, smaller s

Overview of sorting methods