Counting Sort
Algorithm
Input Array of integers Output Sorted array Complexity O(n). COUNTING-SORT(A, B, k) 1 for i ← 0 to k 2 do C[i] ← 0 3 for j ← 1 to length[A] 4 do C[A[j]] ← C[A[j]] + 1 5 C[i] now contains the number of elements equal to i. 6 for i ← 1 to k 7 do C[i] ← C[i] + C[i - 1] 8 C[i] now contains the number of elements less than or equal to i. 9 for j ← length[A] downto 1 10 do B[C[A[j]]] ← A[j] 11 C[A[j]] ← C[A[j]] - 1
Algorithm Description
1. Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k 2. Performs counting sort on array A of size n. Array c keep traks of the count of each element 3. B is the output array which have sorted element
