Sorting in linear time Counting sort: no comparisons between elements Input:A[l..nl, where a∈{1,2,…,k} Output: B[1.nI, sorted Auxiliary storage: C[l. k o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.11© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.11 Sorting in linear time Counting sort: No comparisons between elements. • Input: A[1 . . n], where A[j]∈{1, 2, …, k} . • Output: B[1 . . n], sorted. • Auxiliary storage: C[1 . . k]