Nuts and Bolts 2

"""
class Comparator:
    def cmp(self, a, b)
You can use Compare.cmp(a, b) to compare nuts "a" and bolts "b",
if "a" is bigger than "b", it will return 1, else if they are equal,
it will return 0, else if "a" is smaller than "b", it will return -1.
When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
"""

from random import randint
class Solution:
    # @param nuts: a list of integers
    # @param bolts: a list of integers
    # @param compare: a instance of Comparator
    # @return: nothing
    def sortNutsAndBolts(self, nuts, bolts, compare):
        # write your code here
        self.sort(nuts, bolts, 0, len(nuts)- 1, compare)


    def sort(self,nuts,bolts,l,r,compare):
        if l>=r:
            return

        i,j=l,r
        cur_nut=None
        pivot=bolts[l]
        while i<=j:
            while i<=j and compare.cmp(nuts[i],pivot)==-1:
                i+=1
            while i<=j and compare.cmp(nuts[j],pivot)==1:
                j-=1
            if i<=j:
                nuts[i],nuts[j]=nuts[j],nuts[i]
                i+=1
                j-=1

        if compare.cmp(nuts[i],pivot)==0:
            cur_nut=nuts[i]
        elif compare.cmp(nuts[i-1],pivot)==0:
            cur_nut=nuts[i-1]

        #print(pivot,nuts,i,j)

        print(pivot,cur_nut,nuts,i,j)
        i,j=l,r
        while i<=j:
            while i<=j and compare.cmp(cur_nut,bolts[i])==1:
                i+=1
            while i<=j and compare.cmp(cur_nut,bolts[i])==-1:
                j-=1
            if i<=j:
                bolts[i],bolts[j]=bolts[j],bolts[i]
                i+=1
                j-=1

        self.sort(nuts,bolts,l,j,compare)
        self.sort(nuts,bolts,i,r,compare)