I'm looking for a fast algorithm for sorting an array of integers with respect to a master list.
For example:
Master List: 7 3 9 1 32 6 5 4 99 100 201 13
Array that needs to be sorted array1: 1 5 4 3 6
The "sorted" array would be: 3 1 6 5 4
The order of the array that needs to sorted is originally random. Neither the master list nor the array that needs to be sorted will have repeating elements.
The fastest algorithm I have right now is:
Sort array1 with quicksort (n lg n)
foreach element in master list{
search for it in array1 //(lg n)
if found add to array2
}
array2 has the "sorted" list I am looking for
Unfortunately this gives worst case time n*lg(n) + m*lg(n) where n=number of elements in array 1 and m = number of elements in master list
and m is really big :(