merge_sort speedy solution for Count Inversions by ciel - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

merge_sort solution in Speedy category for Count Inversions by ciel

def M(l,r):
    if l+1>=r: return 0
    if l+2==r:
        if A[l]<=A[l+1]: return 0
        A[l],A[l+1]=A[l+1],A[l]
        return 1
    m = (l+r)//2
    i=l
    j=m
    k=l
    cl=M(l,m)
    cr=M(m,r)
    c=0
    while i
                        Sept. 3, 2014

                        
                            Comments:
                            
                                
                                    acman
 on Sept. 3, 2014, 6:20 p.m.

                                    <p>It's really speedy?</p>

                                
                            
                                
                                    ciel
 on Sept. 4, 2014, 5:14 a.m.

                                    <p>It's calculation order is O(nlogn). Usual solution takes O(n^2).</p>

                                
                            
                                
                                    tommycarstensen
 on April 24, 2015, 9:28 p.m.

                                    <p>Did you post this in the comment box to all the questions? :)</p>

                                
                            
                                
                                    nickie
 on Sept. 16, 2014, 9:40 p.m.

                                    <p>Well done.  I have a slightly slower version (more Pythonic in the merging phase) with comments and longer variable names.</p>

<p>And (answering to acman), yes, this is faster than the obvious solution by exactly the same amount that mergesort is faster than bubblesort.  If you think of it, counting inversions is a problem very similar to sorting.</p>

List, list and list again

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.