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 it takes a base as a parameter rather than assuming that it is 10. Also modify the function 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.