Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
1
 
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
share|improve this question
Do you mean it to be a simple code review? Or is there any specific aspect of the code that you would like reviewed? – rahul Jun 22 '12 at 7:12
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. – user1468092 Jun 22 '12 at 7:16
The code doesn't work as expected: change unsorted -> u_list – cat_baxter Jun 22 '12 at 9:56

2 Answers

up vote 4 down vote accepted

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.

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

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

    result.extend(l if l else r)
    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]
share|improve this answer
up vote 1 down vote

129 chars version including the file reading :)

import sys, bisect

a = map(int,open(sys.argv[1]))
b = sorted(a)
r = 0
for d in a:
    p = bisect.bisect_left(b,d)
    r += p
    b.pop(p)
print r
share|improve this answer
1  
This isn't codegolf.SE! I would assume "minimalistic" wasn't meant to mean "devoid of whitespace." – Corbin Jun 22 '12 at 8:53
Sorry, corrected :) – cat_baxter Jun 22 '12 at 9:03
This question is tagged as homework, so this probably is not too useful to the OP – Daenyth Jun 24 '12 at 12:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.