Sorting an array based on comparison with another array of same elements in different order

Question

Given two arrays

a[] = {1,3,2,4} 
b[] = {4,2,3,1} 

both will have the same numbers but in different order. We have to sort both of them. The condition is that you cannot compare elements within the same array.

Answer 1

I can give you an algorithm of O(N*log(N)) time complexity based on quick sort.

1. Randomly select an element a1 in array A
2. Use a1 to partition array B, note that you only have to compare every element in array B with a1
3. Partitioning returns the position b1. Use b1 to partition array A (the same as step 2)
4. Go to step 1 for the partitioned sub-arrays if their length are greater than 1.

Time complexity: T(N) = 2*T(N/2) + O(N). So the overall complexity is O(N*log(N)) according to master theorem.

Answer 2

Not sure I understood the question properly, but from my understanding the task is a follows:

Sort a given array a without comparing any two elements from a directly. However we are given a second array b which is guaranteed to contain the same elements as a but in arbitrary order. You are not allowed to modify b (otherwise just sort b and return it...).

In case the elements in a are distinct this is easy: for every element in a count how many elements in b are smaller. This number gives us the (zero based) index in a sorted order.

The case where elements are not necessarily distinct is left to the reader :)