CODEWITHSUNDEEP
pythonmergesort
user672009
user672009

Reputation: 4585

Buggy Merge Sort

Below is my Merge function which is suppose to resemble what is shown in CLRS on page 31. For now I have commented out the code which would handle any remaining list items.

If I pass A = [1, 2, 1, 12, 2, 5] as input. The output is [1, 2, 1, None, None, None].

Can anyone shred some light on what I'm doing wrong?

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        MergeSort(left)
        MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)

Upvotes: 1

Views: 108

Answers (1)

tijko
tijko

Reputation: 8292

When calling MergeSort you are recursively returning new lists but, are never assigning them:

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        #MergeSort(left)
        # here should be
        left = MergeSort(left)
        #MergeSort(right)
        # here should be
        right = MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)

Upvotes: 2

Related Questions