We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I was having problems in Python 3 where I would keep calling len() to get the length of my current array for each loop I was doing. When I initialized two variables with "l = len(left)" and "r = len(right)" at the beginning of my merging function, the time seemed to reduce enough to pass all test cases. Here is what I mean by that:
def merge(left, right, inversions):
new = []
i = j = 0
if left == None: left = []
if right == None: right = []
l = len(left)#!!!!!!!!!
r = len(right)#!!!!!!!!
while i < l and j < r: #before while i < len(left) and j < len(right)
if left[i] <= right[j]:
new.append(left[i])
i += 1
else:
inversions[0] += (l - i)
new.append(right[j])
j += 1
while i < l: #before: while i < len(left)
new.append(left[i])
i += 1
while j < r: #before: while j < len(right)
new.append(right[j])
j += 1
return new
Previously, when I was using "while i < len(left) and j < len(right)", "while i < len(left)" and "while j < len(right) " the program would not pass all test casses (although, I wouldn't think the len() function actually takes that long).
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
I was having problems in Python 3 where I would keep calling len() to get the length of my current array for each loop I was doing. When I initialized two variables with "l = len(left)" and "r = len(right)" at the beginning of my merging function, the time seemed to reduce enough to pass all test cases. Here is what I mean by that:
def merge(left, right, inversions): new = [] i = j = 0 if left == None: left = [] if right == None: right = [] l = len(left)#!!!!!!!!! r = len(right)#!!!!!!!!
Previously, when I was using "while i < len(left) and j < len(right)", "while i < len(left)" and "while j < len(right) " the program would not pass all test casses (although, I wouldn't think the len() function actually takes that long).
Hope this clarified my post.