# Question: some sorting algorithms are not stable duplicate keys relative order...

###### Question details

Some sorting algorithms are NOT stable (duplicate keys relative order is preserved after sorting). However if every key in A[i] is changed to A[i]*n + i - 1 (assume 1<=i<=n ) then all the new elements are distinct (and therefore stability is no longer a concern). After sorting, what transformation will restore the keys back to their original values? What is the effect on the runtime of any of the sorting algorithms if you add this transformation before executing the sort and un-transformation after the sort?