Sorting In Linear Time
Sorting
• Sort n integers in
• Merge Sort, Heap Sort in the worst case
• Quick Sort on average
• Compare elements to determine the sorted order
• Called comparison sorts
Lower Bounds for Sorting
• Comparison sorts gains order information from
comparisons
• Doesn’t inspect values
• Given and , test , , , , or
• For lower bound analysis,
• All elements are distinct
Lower Bounds for Sorting
• The decision tree model
• A full binary-tree
• Node is either a leaf or has a >=b
both children
• Node represents the Yes No
comparisons between two Do
elements Do
Something
Something
Else
Lower Bounds for Sorting
• The decision tree model
• Leaf indicates a
permutation of n elements
• Internal nodes are
annotated as
• Internal node indicates a
comparison
Lower Bounds for Sorting
• Any correct sorting
algorithm must be able to
produce each permutation
of its input
• Each of the permutations
on n elements must
appear as at least one of
the leaves
Lower Bounds for Sorting
• Worst-case comparisons
• Longest simple path length
from the root to any of its
reachable leaves
• Equals the height of the
decision tree
• Can we estimate a bound
of the height of such
decision trees?
Lower Bounds for Sorting
• Any comparison sort algorithm requires comparisons in
the worst case.
• Proof:
• A binary tree of height h has no more than leaves
• Merge sort and Heapsort are asymptotically optimal
algorithms
Counting Sort
• Assumes that inputs are integers in the range 0 to k
• For an input x,
• Determine the number of elements less than or equal to
x
• Place element x directly into its position in the output
array
• Runs in
• How to handle duplicates?
Counting Sort
Counting Sort
A
2 5 3 0 2 3 0 3
C
2 0 2 3 0 1
Counting Sort
A
2 5 3 0 2 3 0 3
C (old)
2 0 2 3 0 1
C(current state)
2 2 4 7 7 8
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
2 2 4 7 7 8
B
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
2 2 4 7 7 8
B
3
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
2 2 4 6 7 8
B
3
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
2 2 4 6 7 8
B
0 3
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
1 2 4 6 7 8
B
0 3
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
1 2 4 6 7 8
B
0 3 3
Counting Sort
A
2 5 3 0 2 3 0 3
C(current state)
0 2 2 4 7 7
B
0 0 2 2 3 3 3 5
Counting Sort
• Counting sort is stable
• Elements with the same value appear in the output array in
the same order as they do in the input array.
Radix Sort
• We can sort the elements
• By most significant (leftmost) digit
• Then sort the resulting bins recursively
• Finally combine the bins in order.
• Generates many intermediate bins to track
Radix Sort
• Let’s start by the least significant bit
• For example,
Radix Sort
Radix-sort sorts n d-digit number in
Bucket Sort
• Assumes that the input is uniformly distributed in a range
• Divides the range into n equal-sized subintervals, or
buckets
• Distributes the inputs into the buckets
• The inputs are uniformly distributed
• Expected number of input per bucket is low
• Sort the numbers in each bucket
• Go through the buckets in order, listing the elements in
each
Bucket Sort
Bucket Sort
• Runs in
Reference
• Sorting in Linear Time
• CLRS 4th Ed. Chapter 8
