Inversion count using merge sort

Question

count = 0
def merge_sort(li):
 if len(li) < 2: return li 
 m = len(li) / 2 
 return merge(merge_sort(li[:m]), merge_sort(li[m:])) 
def merge(l, r):
 global count
 result = [] 
 i = j = 0 
 while i < len(l) and j < len(r): 
 if l[i] < r[j]: 
 result.append(l[i])
 i += 1 
 else: 
 result.append(r[j])
 count = count + (len(l) - i)
 j += 1
 result.extend(l[i:]) 
 result.extend(r[j:]) 
 return result
unsorted = [10,2,3,22,33,7,4,1,2]
print merge_sort(unsorted)
print count

• Rahul Gopinath: Do you mean it to be a simple code review? Or is there any specific aspect of the code that you would like reviewed?
• user1468092: I just want the code to be minimalistic and also readable... so if there is any improvement in that aspect then I would definitely like some positive criticism.
• cat_baxter: The code doesn't work as expected: change unsorted -> u_list
• ofer.sheffer: Some of the following suggestions make the error of using pop(0). Unlike pop(), which pops the last element and takes O(1), s.pop(0) gives O(n) runtime (rearranging the positions of all other elements). This breaks the algorithmic O(nlogn) concept and turns the runtime to O(n^2).
• ofer.sheffer: Added my own version for codereview here: codereview.stackexchange.com/questions/107928/…

Answer 1

Rather than a global count, I would suggest using either a parameter, or to return a tuple that keeps the count during each recursive call. This would also assure you thread safety.

def merge_sort(li, c):
 if len(li) < 2: return li 
 m = len(li) / 2 
 return merge(merge_sort(li[:m],c), merge_sort(li[m:],c),c) 
def merge(l, r, c):
 result = []

Since l and r are copied in merge_sort, we can modify them without heart burn. We first reverse the two lists O(n) so that we can use s.pop() from the correct end in O(1) (Thanks to @ofer.sheffer for pointing out the mistake).

 l.reverse()
 r.reverse()
 while l and r:
 s = l if l[-1] < r[-1] else r
 result.append(s.pop())

Counting is separate from the actual business of merge sort. So it is nicer to move it to a separate line.

 if (s == r): c[0] += len(l)

Now, add what ever is left in the array

 rest = l if l else r
 rest.reverse()
 result.extend(rest)
 return result
unsorted = [10,2,3,22,33,7,4,1,2]

Use a mutable DS to simulate pass by reference.

count = [0]
print merge_sort(unsorted, count)
print count[0]

• ofer.sheffer: Unlike pop(), which pops the last element and takes O(1), s.pop(0) gives O(n) runtime (rearranging the positions of all other elements). This breaks the algorithmic O(nlogn) concept and turns the runtime to O(n^2).
• Rahul Gopinath: Thank you, I did not realize that. Since it is a major problem, would you like to make an answer of your own (I will note your comment in my answer, and point to yours if you do that)?
• ofer.sheffer: I added my own version for code review here: codereview.stackexchange.com/questions/107928/… - I used a loop over k values (subarray). For each of them I run "A[write_index]=value" which is O(1).