simplest mergesort implementation in Python, having type troubles

Question

I wrote a simple mergesort implementation for learning purpose, but it doesen't work. Even if I go through the code step by step, I don't know why the type problem arises. Here is my code:

def mergesort(seq):
    if len(seq)<2:
        return seq
    else:
        m = len(seq)//2
        return merge(mergesort(seq[:m]), mergesort(seq[m:]))

def merge(low, high):
    res = []
    i, j = 0, 0
    while i<len(low) and j<len(high):
        if low[i] <= high[j]:
            res.append(low[i])
            i = i+1
        else:
            res.append(high[j])
            j = j+1
    res.append(low[i:])
    res.append(high[j:])
    return res

and this is what the python-shell returns:

>>> mergesort([5,8,1,3,99,5,2,3,4,9,7,5,8])
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    mergesort([5,8,1,3,99,5,2,3,4,9,7,5,8])
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 6, in mergesort
    return merge(mergesort(seq[:m]), mergesort(seq[m:]))
  File "D:\Documents\alp2\py2.py", line 12, in merge
    if low[i] <= high[j]:
TypeError: unorderable types: int() <= list()
>>>

Answer 1

The issue is mainly because of the lines -

res.append(low[i:])
res.append(high[j:])

Here, the slicing returns lists , and then you are appending those returned lists into res list, and returning this res list. Hence at sometime, it tries to compare the above added list with an integer causing the issue you are seeing.

To add the elements from the list as elements of the res list. You should use list.extend() instead of .append() . Example -

res.extend(low[i:])
res.extend(high[j:])

---

Demo -

>>> def mergesort(seq):
...     if len(seq)<2:
...         return seq
...     else:
...         m = len(seq)//2
...         return merge(mergesort(seq[:m]), mergesort(seq[m:]))
...
>>> def merge(low, high):
...     res = []
...     i, j = 0, 0
...     while i<len(low) and j<len(high):
...         if low[i] <= high[j]:
...             res.append(low[i])
...             i = i+1
...         else:
...             res.append(high[j])
...             j = j+1
...     res.extend(low[i:])
...     res.extend(high[j:])
...     return res
...
>>>
>>> mergesort([10,12,55,22,100])
[10, 12, 22, 55, 100]
>>> mergesort(list(range(100,50,-10)))
[60, 70, 80, 90, 100]