python - Two Implementations of MergeSort with Vastly Different Running TImes -

i beginner learning algorithms fun, , trying implement merge sort in python.

below implementation. slow when feed 100000 list.

def mergesortedlist(l, r):     lr = [0]*(len(l)+len(r))  ##merged output (lr combined)     i= 0     ##counter left side     j= 0      ##counter ride side     k = 0     while <= len(l) , j <= len(r):          if == len(l):              lr[k:]= r[j:]             return lr          elif j == len(r):              lr[k:] = l[i:]             return lr         elif l[i] < r[j]:              lr[k]= l[i]             i+=1             k+=1         else: ##left side bigger right side             lr[k]=r[j]             j+=1             k+=1     def mergesort(n):        if len(n) <= 1:          return n     else:         sub1 = n[0:round(len(n)/2)]           sub2 = n[round(len(n)/2):]         return mergesortedlist(mergesort(sub1), mergesort(sub2)) 

here's implementation found somewhere online website (http://interactivepython.org/courselib/static/pythonds/sortsearch/themergesort.html)

def mergesort(alist):     print("splitting ",alist)     if len(alist)>1:         mid = len(alist)//2         lefthalf = alist[:mid]         righthalf = alist[mid:]          mergesort(lefthalf)         mergesort(righthalf)          i=0         j=0         k=0         while < len(lefthalf) , j < len(righthalf):             if lefthalf[i] < righthalf[j]:                 alist[k]=lefthalf[i]                 i=i+1             else:                 alist[k]=righthalf[j]                 j=j+1             k=k+1          while < len(lefthalf):             alist[k]=lefthalf[i]             i=i+1             k=k+1          while j < len(righthalf):             alist[k]=righthalf[j]             j=j+1             k=k+1     print("merging ",alist)  alist = [54,26,93,17,77,31,44,55,20] mergesort(alist) print(alist) 

it's fast.

from can tell, implementation o(nlog(n)), why mine slower?

thanks help.

cheers!

i don't see huge performance difference: 7.3s vs 5.4s 1,000,000 random floats. you're correct second 1 faster.

here's how profile them see what's taking time.

python -m cprofile -s time mergesort.py 

output yours:

999999    8.517    0.000   11.088    0.000 mergesort.py:2(mergesortedlist) 1999999/1    2.735    0.000   14.151   14.151 mergesort.py:25(mergesort) 84184856/84184834    2.725    0.000    2.725    0.000 {len} 1999998    0.174    0.000    0.174    0.000 {round} 

and second one:

ncalls  tottime  percall  cumtime  percall filename:lineno(function) 1999999/1    7.377    0.000    8.721    8.721 mergesort2.py:1(mergesort) 40499148/40499126    1.344    0.000    1.344    0.000 {len} 

you see yours spends more time calling len() , round().

also second 1 operates on array passed reference while yours returns array. copying may take time too. since you're beginner make sense review difference