Problem

Given two Lists (or arrays) A and B, all the elements in each A or B cannot be compared. Therefore, one cannot sort the elements in A and the elements in B in this case.

However, one knows that one can compare each element in A with that in B with a function, compare_function, which returns -1, 0 or 1 if element in A is smaller, equal to, or larger than that in B.

Besides, we know that the sorted A is identical to sorted B.

Using the above information to sort A and B.

Code

brute force

class Solution(object):
    
    def Sort_List(self,ListA,ListB):
        
        """
        ListA=[a1,a2,a3,...]
        ListB=[b1,b2,b3,...]
        """
        
        # define a function for the comparison
        def compare_function(a,b):
            if a>b:
                return 1
            elif a==b:
                return 0
            else:
                return -1
        
        # Here I am going to use the brute-force method to sort the ListA and ListB.
        # The time complexity will be O(n^2)
        
        # define two dictionaries
        dic4A ={}
        dic4B ={}
        
        for idxa,a in enumerate(ListA):
            
            # The dictionary dic4A is to count the numbers 
            # of elements in ListB which are smaller than each element in ListA
            
            dic4A[a] = 0
            
            for idxb,b in enumerate(ListB):
                
                if compare_function(a, b) == 1:
                    dic4A[a] += 1 
                    
                elif compare_function(a, b)== 0:
                    dic4B[a] = idxb       # record the a in the position of ListB
                    
        # Although all the a in ListA (namely, the key in dic4A) cannot be compared with each other,
        # the value of the each key-value pair in the dic4A can be sorted.
        # For simplicity, I use the python built-in function sorted() for this purpose,
        # the time complexity is O(n log n)
        sorted_dic4A = sorted(dic4A.items(), key=lambda x: x[1])
        sorted_ListA = [x[0] for x in sorted_dic4A]
        
        
        # sort the ListB based on the connection between ListA and ListB
        sorted_ListB=[]
        for i in range(0,len(ListB)):
            
            val_i  = sorted_dic4A[i][0]
            idxb_i = dic4B[val_i] 
            sorted_ListB.append(ListB[idxb_i])
            
        
        return sorted_ListA,sorted_ListB   

quick sort

import random

# define a function for the comparison
def compare_function(a,b):
    if a>b:
        return 1
    elif a==b:
        return 0
    else:
        return -1
            
def partition(AB, p, r, i_ref):
    (AB[i_ref], AB[r]) = (AB[r], AB[i_ref])
    
    ref = AB[r]
    j = p - 1
    
    for i in range(p,r):
        if compare_function(AB[i],ref)<=0:
            j = j + 1
            (AB[j], AB[i]) = (AB[i], AB[j])
    (AB[j+1], AB[r]) = (AB[r], AB[j+1])
    
    return j+1

def linked_partition(A,B,p,r):
    i = random.randint(p,r)
    
    for j in range(p, r+1):
        if compare_function(A[i],B[j]) ==0:
            (B[j], B[i]) = (B[i], B[j])
            return i
        
def quick_sort(A,B,p,r):
    if p<r:
        i_ref = linked_partition(A,B,p,r)
        i_A = partition(A, p, r, i_ref)
        i_B = partition(B, p, r, i_ref)
        
        if i_A != i_B:
            return print('error')
        
        quick_sort(A, B, p, i_A-1)
        quick_sort(A, B, i_A+1, r)

Test

For the sake of simplicity and test

listA=[6,7,3,5,2,4]
listB=[3,4,2,5,7,6]

test brute-force method

print(listA, listB)

[6, 7, 3, 5, 2, 4] [3, 4, 2, 5, 7, 6]

solve = Solution()

solve.Sort_List(listA,listB)

([2, 3, 4, 5, 6, 7], [2, 3, 4, 5, 6, 7])

test quick_sort

print(listA, listB)

[6, 7, 3, 5, 2, 4] [3, 4, 2, 5, 7, 6]

quick_sort(listA,listB,0,len(listA)-1)

print(listA, listB)

[2, 3, 4, 5, 6, 7] [2, 3, 4, 5, 6, 7]