changing a black box array sorting algorithm to be a stable algorithm

Question

let Sort1 be a given algorithm and A a given array. Sort1 run in time of f(n). I need to create a new stable algorithm, Sort2, using Sort1 that will run in time of f(n)+O(n).

I have a solution my friend suggested:

• Creating a clone array B of A.
• Changing every number in B to a couple (number,index) where number is the number (the element), and index is it's index (location in A).
• every element in B points to it's corresponding element in A.
• run Sort1 on A.
• for every sequence of same numbers in sorted A, run Sort1 on the flash that will sort the flash by the index of every element.

is his solution right? do you have any suggestions? thanks!

Answer 1

Make your copy, but then create a new comparison function that uses the original data as the primary key (probably even using the original comparison function to do the comparison), and if that's equal, have it do a secondary comparison based on the original position in the array.