Mergesort problem

Deborah Swanson python at deborahswanson.net
Wed Dec 21 19:55:18 EST 2016


I'm not a beginning python coder, but I'm not an advanced one either. I
can't see why I have this problem, though at this point I've probably
been looking at it too hard and for too long (several days), so maybe
I'm just too close to it.
Can one of you guys see the problem (besides my childish coding)? I'll
give you the code first, and then the problem.

def moving():
    import csv
    ls = []
    with open('E:\\Coding projects\\Pycharm\\Moving\\New Listings.csv',
'r') as infile:
        raw = csv.reader(infile)
        indata = list(raw)
        rows = indata.__len__()
    for i in range(rows):
        ls.append(indata[i])
    # sort: Description only, to make hyperelinks & find duplicates
    mergeSort(ls)
    # find & mark dups, make hyperlink if not dup
    for i in range(1, len(ls) - 1):
        if ls[i][0] == ls[i + 1][0]:
            ls[i][1] = "dup"
        else:
            # make hyperlink
            desc = ls[i][0]
            url = ls[i][1]
            ls[i][0] = '=HYPERLINK(\"' + url + '\",\"' + desc + '\")'
    # save to csv
    ls.insert(0, ["Description","url"])
    with open('E:\\Coding projects\\Pycharm\\Moving\\Moving 2017
out.csv', 'w') as outfile:
        writer = csv.writer(outfile, lineterminator='\n')
        writer.writerows(ls)

import operator
def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

def merge(left, right, compare):
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

moving()

The problem is that while mergeSort puts the list ls in perfect order,
which I can see by looking at result on merge's final return to
mergeSort, and at the left and the right once back in mergeSort. Both
the left half and the right half are in order. But the list L is still
in its original order, and after mergeSort completes, ls is still in its
original order. Maybe there's some bonehead error causing this, but I
just can't see it.

I can provide a sample csv file for input, if you want to execute this,
but to keep things simple, you can see the problem in just a table with
webpage titles in one column and their urls in the second column.

Any insights would be greatly appreciated.



More information about the Python-list mailing list