Sorting N /Slide 10 Counting sort Assume n integers are to be sorted, each is in the range 1 to M Define an array b[1.M], initialize all toO O(M) Scan through the input list A[, insert A[] into B[AQI= O(N) Scan B once, read out the nonzero integers= O(M) otal time: O(M+ N) if M is o(n), then total time is O(N) Can be bad if range is very big, e.g. M=O(N2) N=7,M=9, Want to sort 8 19 526 3 11235689 Output: 123568 9Sorting IV / Slide 10 Counting Sort Assume N integers are to be sorted, each is in the range 1 to M. Define an array B[1..M], initialize all to 0  O(M) Scan through the input list A[i], insert A[i] into B[A[i]]  O(N) Scan B once, read out the nonzero integers  O(M) Total time: O(M + N) if M is O(N), then total time is O(N) Can be bad if range is very big, e.g. M=O(N2 ) N=7, M = 9, Want to sort 8 1 9 5 2 6 3 1 2 5 8 9 Output: 1 2 3 5 6 8 9 3 6