(Solved): A stable sorting algorithm is one in which the relative order of all identical elements (or keys) ...

A stable sorting algorithm is one in which the relative order of all identical elements (or keys) is the same in the output as it was in the input. For example, a stable sorting of array \( \left[2,3,5,2^{\prime}, 4,5^{\prime}\right] \) gives \( \left[2,2^{\prime}, 3,4,5,5^{\prime}\right] \). a) Indicate whether quick sort is stable or not. You need to justify your answer via a counter-example or a proof. Assume we select the pivot to be the first element in the subarray we are sorting, and we use the Partition algorithm in slide 41 of the Sorting module. b) An application of stable sorting is in Radix sort. The idea is to sort a set if integers, iteratively and digit by digit (often starting from the least significant digit, moving towards most significant digit). In the \( i \) 'th iteration, a stable sorting method \( A \) is used to sort items based on their \( i \) 'th digit; given that the \( A \) is stable, at the end of the \( i \) th iteration, the numbers will be sorted with respect to their rightmost \( i \) digit. Here is an example: Note that if a linear-time stable sorting algorithm is used as \( A \), the running time of Radix Sort will be \( \Theta(n \times b) \). Apply Radix Sort to sort the following input. Show your work.