9
\$\begingroup\$
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
\$\endgroup\$
5
  • \$\begingroup\$ Do you mean it to be a simple code review? Or is there any specific aspect of the code that you would like reviewed? \$\endgroup\$ Jun 22, 2012 at 7:12
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 22, 2012 at 7:16
  • \$\begingroup\$ The code doesn't work as expected: change unsorted -> u_list \$\endgroup\$
    – cat_baxter
    Jun 22, 2012 at 9:56
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ Oct 18, 2015 at 8:14
  • \$\begingroup\$ Added my own version for codereview here: codereview.stackexchange.com/questions/107928/… \$\endgroup\$ Oct 19, 2015 at 5:56

1 Answer 1

7
\$\begingroup\$

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]
\$\endgroup\$
3
  • \$\begingroup\$ 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). \$\endgroup\$ Oct 18, 2015 at 8:12
  • \$\begingroup\$ 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)? \$\endgroup\$ Oct 18, 2015 at 23:02
  • \$\begingroup\$ 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). \$\endgroup\$ Oct 19, 2015 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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