Algorithm for sorting array of integers w/ respect to another array (c code would be

[tc18a]

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 :(

[Banfa]

Either use a single array of structures rather than 2 arrays of int and pass it to qsort or write your own sort algorithm, everytime you perform a swap in array1 do the same swap in array2 and array2 will maintain the correct sorting relative to array1.

[newb16]

I could not understand this : >The "sorted" array would be: 3 1 6 5 4
What is sort predicate like to get this order for 'sorted' array? If you need to get all numbers from masterlist that are also in A1, in the same order they are in masterlist, just make a hashtable of A1 and check each element of masterlist against it.

[donbock]

What should happen if the "array to be sorted" contains a value that is not in the master list? I'll assume that this is not allowed ...

Construct an associative array M indexed by the values in the master list where each value in M is the corresponding index into the master list. Unfortunately, C doesn't support associative arrays so you will have to be creative (perhaps a sparse array or a hash).

Create a compare function for quicksort that compares two values in "the array to be sorted" by using those values to index into the associative array M and comparing the values found there.

Constructing the associative array has to be close to O(m), and accessing elements in the associative array has to be close to O(1), for this to be a helpful suggestion. If you can manage that then you can achieve overall efficiency O(m + nlogn).

[jkmyoung]

Constructing the associative array is O(mlogm) at best, unless you are using bucket sort and m is close to the maximum value for your integers.

You can do no better than your original algorithm since m is not sorted, and does not have an associative array.
If you were to construct an associative array, you would get
m log m + n log m vs
m log n + n log n

which is worse by more than a factor of log m/log n (since the constant for sorting is bigger than searching)

It may be worthwhile to create a sorted associative array if you intend on doing this task with different arrays, as you would only have to pay the O(m log m) cost once.

[tc18a]

I figured out n lg(n) algorithm;

I created a new array called location[].
While I am creating my master list, I store the location of each data value into location. For example, if in the master list 5 is in location 10, I do location[5] = 10. Now I have a way of looking up the location of any data value in constant time.

I then did a qsort(array1, length of array1, sizeof(int), compare);

Where compare is:
{
return location[a] - location[b]
}

qsort here gives n log n (array1 is pretty random and has unique values) and no dependency on M anymore. :)

Thanks for all the responses!

[jkmyoung]

I assume there was another restriction we were not told of, such as the master list contains all the numbers from 1 to n. Then the associative array is made in O(m) time.