up vote 3 down vote favorite

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!

share|improve this question
50% accept rate
I'm sorry, but what's a flash? – Fezvez Jun 30 '11 at 16:08
feedback

1 Answer

up vote 5 down vote

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.

share|improve this answer
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.