USE PYTHON PLEASE AND FOLLOW THE RULES!

Problem 3 (Counting Sort) In general, the best performance you can hope to accomplish with sorting is an O(n log n) solution. When you know that the number of unique values you will be sorting is relatively small compared to the size of the list (n), you can improve on this solution by using a method called counting sort. The general premise of counting sort is as follows: 1. lterate over the list one time and count the frequency of each value that occurs. This can be done in O(n) time 2. Sort the list of unique values, which is much smaller than the size of the list, and therefore much faster to sort. This can be done in O(k log k) time, where k is the