0
\$\begingroup\$

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?

\$\endgroup\$

closed as off-topic by πάντα ῥεῖ, t3chb0t, Mast, alecxe, Edward May 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.

  • 4
    \$\begingroup\$ "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? \$\endgroup\$ – Mast May 7 '17 at 15:58
3
\$\begingroup\$

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).

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
  • 2
    \$\begingroup\$ This is only marginally better: the insertion in the middle of deque is still linear, and the entire algorithm remains above quadratic. \$\endgroup\$ – vnp May 7 '17 at 18:01

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