Please answer the questions correctly and and show clear and easy explained detailed workings explaining steps. Please really make sure its correct.

2. (6 pts) (a) Give an algorithm that takes an unsorted array A of n numbers and outputs the k small- est numbers in sorted order. For full marks, your algorithm should run in O(n +klog k) time. Slower solutions will get part marks. Hint: You may use any algorithm from class as a black box (b) Why is your algorithm correct? (c) Analyse the running time of your algorithm