Mergesort Python numerical ordering in a list

Question

I am trying to implement the mergesort algorithm in Python. My input, file.txt, is of the form:

However, my output becomes (notice the second element of the list):

[['1'], ['19'], ['2'], ['3'], ['4'], ['5'], ['55'], ['60'], ['82']]

Can someone please explain why this implementation of mergesort fails to place the 19 into its proper location in the Python list?

import csv

list = []
with open('file.txt') as f:
    lines = csv.reader(f, delimiter='\n')
    for line in lines:
        list.append(line)

def mergesort(list):
    mid = len(list)//2
    lft, rgt = list[:mid], list[mid:]
    if len(lft) > 1: lft = mergesort(lft)
    if len(rgt) > 1: rgt = mergesort(rgt)
    res = []
    while lft and rgt:
        if lft[-1] >=rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
    res.reverse()
    return (lft or rgt) + res

print mergesort(list)

Avoid naming your variable using Python keyword, for example `list = []` — Iron Fist, Jul 06 '15 at 02:59
`list` is *not* a Python keyword: http://stackoverflow.com/questions/14595922/list-of-python-keywords — warship, Jul 06 '15 at 03:02

Matthew King · Accepted Answer · 2015-07-06T03:00:27.137

6

I think this should explain what is happening:

matt$ python
>>> '19' < '2'
True
>>> int('19') < int('2')
False

When comparing strings, the string '19' is less than the string '2' because the character '1' comes before the character '2'.

If you convert the strings to numbers, the sorting should come out correctly.

edited Jul 06 '15 at 03:00

answered Jul 06 '15 at 02:54

Matthew King

1,342
7
13

Mergesort Python numerical ordering in a list

1 Answers1