CODEWITHSUNDEEP
sortingtime-complexitymergesort
Soufiane
Soufiane

Reputation: 368

Why is my mergesort implementation slower than bubble sort and insertion sort?

I'm trying to compare the complexity in time (time execution) of different sorting algorithms. I'm comparing bubble sort, insertion sort, quick sort, and fusion sort (mergesort).

I know that merge sort and quick sort are faster than the others, but when I try to compare execution time of these methods, the merge sort always take much more time than all the others. I tried with lists of 1,000 elements to 10,000 elements. Can anyone tell me why?

Here is my mergesort code:

def inserer(element, ls):
   if  ls==[]:
       return [element]
   elif element<= ls[0]:
       return [element] + ls
   else:
       return [ls[0]] + inserer(element, ls[1:len(ls)])

def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))


def triFusion (ls):
   n=len(ls)
   if n==0 or n==1:
       return ls
   else:
       return fusion(triFusion(ls[0:n//2]),triFusion(ls[n//2:n]))

Upvotes: 0

Views: 681

Answers (1)

templatetypedef
templatetypedef

Reputation: 372714

I think that the issue here is that your merge (fusion) function is implemented in a way that makes it much, much slower than it needs to be. Here's your code:

def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))

Your code is implemented by repeatedly taking the first element of L1, inserting it into L2 by doing a linear search, then repeating. The time complexity of this approach is O(n2) in the worst case, since the first insertion might have to scan over n elements to find the proper place for the element, the second might have to scan over n + 1, the third n + 2, etc.

This breaks the nice time bounds you normally get with mergesort. Typically, the merge operation is implemented to take time O(n). Since mergesort makes two recursive calls on arrays half as large as the original and then calls merge, the normal time complexity of mergesort obeys this recurrence:

T(n) = 2T(n / 2) + O(n)

which, using the master theorem, solves to O(n log n). However, in your case, since your merge step takes time O(n2), the runtime is

T(n) = 2T(n / 2) + O(n2)

which the master theorem says solves to O(n2). In other words, the time complexity of your implementation is quadratic, just like bubble sort and insertion sort, but likely has a much higher constant factor due to the fact that it makes lots and lots of calls to an inefficient algorithm.

To fix this, try rewriting your merge algorithm to run in linear time. That will likely make your code run much, much faster.

Upvotes: 1

Related Questions