# Could this be considered a valid mergesort? [closed]

I tried to do a mergesort function for an assignment without importing merge from heapq:

def mergesort(a):
if len(a) < 2:
return a
return mymerge(mergesort(a[len(a) // 2:]), mergesort(a[:len(a) // 2]))

def mymerge(list1, list2):
for i in range(len(list1)):
for x in range(len(list2)):
if list1[0] < list2[x]:
list2.insert(x, list1[0])
list1.pop(0)
break
if list1[0] > list2[len(list2) - 1]:
list2.append(list1[0])
list1.pop(0)
break
return list2


Could this be considered a valid mergesort or does my function have flaws? Are there ways to improve the mymerge function?

## closed as off-topic by πάντα ῥεῖ, t3chb0t, Mast, alecxe, EdwardMay 7 '17 at 23:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – πάντα ῥεῖ, t3chb0t, Mast, alecxe, Edward
If this question can be reworded to fit the rules in the help center, please edit the question.

• "Could this be considered a valid mergesort" Did you test it? Does it work as such? Is there a reason you're not using the standard sort functions already provided by Python? – Mast May 7 '17 at 15:58

No, it is not a merge sort. It never accounts for the fact that list1 is already sorted. Instead it performs len(list1) insertions, every time traversing list2 from the very beginning.

Each call to mymerge is quadratic with respect to the length of the list). At each recursion level $r$ there are $2^r$ fragments of length $\dfrac{n}{2^r}$, so each recursion level will take $O\left(r\left(\dfrac{n}{2^r}\right)^2\right)$ time, and summing up for $r$ from $1$ to $\log{n}$ yields the total complexity $O\left( n^2 \log{n}\right)$.

The expected runtime of merge sort shall be $O(n\log{n})$ (or $O(n \log^2{n})$ if done in place).

Honestly, this looks pretty good. There are just a couple of things that I would change.

1) The len(list2) - 1 can simply be shortened to -1 as Python supports negative indexing.

2) I would assign the arguments for mymerge to lists

This is the code that I ended up with:

def mergesort(a):
if len(a) < 2:
return a
list_1 = mergesort(a[len(a) // 2:])
list_2 = mergesort(a[:len(a) // 2])
return mymerge(list_1,list_2)

def mymerge(list1, list2):
for i in range(len(list1)):
for x in range(len(list2)):
if list1[0] < list2[x]:
list2.insert(x, list1[0])
list1.pop(0)
break
if list1[0] > list2[-1]:
list2.append(list1[0])
list1.pop(0)
break
return list2


list.pop(0) is $\mathcal{O}(n)$, because all elements must be moved (have a look at the list entry here)

Instead, you should use collections.deque, which has $\mathcal{O}(1)$ popleft() and pop() (so both ends are fine, only inserting/deleting in the middle takes long). Otherwise deque behaves just like a list. You can just convert your list to a deque when passing it to the sort function or make it a deque in the first place.

In addition, mymerge is not a very good name. Just call it merge. Also, mergesort should be merge_sort according to Python's official style-guide, PEP8.

from collections import deque

def merge_sort(a):
if len(a) < 2:
return a
list_1 = merge_sort(a[len(a) // 2:])
list_2 = merge_sort(a[:len(a) // 2])
return merge(list_1,list_2)

def merge(list1, list2):
for i in range(len(list1)):
for x in range(len(list2)):
if list1[0] < list2[x]:
list2.insert(x, list1[0])
list1.popleft()
break
if list1[0] > list2[-1]:
list2.append(list1[0])
list1.popleft()
break
return list2

if __name__ == "__main__":
a = [1,4,1,4,6,8,9,4,2,4,8,9,90,0,5,346,65,47]
merge_sort(deque(a))
b = deque([213,25,34,13,,45,6,4,7])
merge_sort(b)

• This is only marginally better: the insertion in the middle of deque is still linear, and the entire algorithm remains above quadratic. – vnp May 7 '17 at 18:01