Sorting N /Slide 11 Counting sort What if we have duplicates? B is an array of pointers Each position in the array has 2 pointers head and tail. Tail points to the end of a linked list, and head points to the beginning Af] is inserted at the end of the list B[ADlI Again, Array B is sequentially traversed and each nonempty list is printed out Time: O(M+ N)Sorting IV / Slide 11 Counting sort What if we have duplicates? B is an array of pointers. Each position in the array has 2 pointers: head and tail. Tail points to the end of a linked list, and head points to the beginning. A[j] is inserted at the end of the list B[A[j]] Again, Array B is sequentially traversed and each nonempty list is printed out. Time: O(M + N)