Write a function that performs a selection sort on an array, using an arbitrary function to map each array element to a sorting key. Then demonstrate that the sort is not stable by finding an input array and key function such that the output is different than it would be with a stable sort.
Repeat the preceding exercise to show that quicksort with Hoare partitioning is not stable.
Modify the radix sort function from the lecture so that the caller does not need to specify the maximum number of digits k; the function should determine that automatically from the numbers in the input array.
Given n integers in the range 0 ≤ i ≤ n4 – 1, show how it is possible to sort them in O(n) time using O(n) memory.