CODEWITHSUNDEEP
pythonmergesort
Koji
Koji

Reputation: 85

How to fix my merge sort because it reverts my arrays into unsorted ones?

I am trying to make a recursive merge sort function in python, however, my code would not work. It first splits the code into 1 cell arrays then merges and sorts them together. However, on the second level of the merge, the function reverts back to the arrays that have not been sorted. I was wondering how I can adapt my code for my sorting to work.

def merge(list1, list2):
    count1 = count2 = 0
    final = []
    while count1 < len(list1) and count2 < len(list1):
        if list1[count1] <= list2[count2]:
            final.append(list1[count1])
            count1 += 1
        else:
            final.append(list2[count2])
            count2 += 1
    if count1 == len(list1):
        for i in range(count2, len(list2)):
            final.append(list2[i])
    else:
        for i in range(count1, len(list1)):
            final.append(list1[i])
    return final


def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        merge_sort(list1)
        merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        print(merge(list1,list2),"merge")
        return merge(list1, list2)


numbers = [2, 1, 3, 4, 6, 5, 8, 7]
print(merge_sort(numbers))

When I entered in [2, 1, 3, 4, 6, 5, 8, 7], it is separated into multiple cells. Then it is merged and sorted, [1,2], [3,4], [5,6], [7,8]. The next merge, however, reverts the sorting. [2,1] + [3,4] = [2,1,3,4], [6,5] + [8,7] = [6,5,8,7]. It returns [2, 1, 3, 4, 6, 5, 8, 7] at the end.

Upvotes: 5

Views: 112

Answers (4)

chqrlie
chqrlie

Reputation: 144770

You do not store the lists returned from the resursive calls, hence the merge phase operates on the original arrays, and fails.

Here is a corrected version:

def merge(list1, list2):
    count1 = count2 = 0
    final = []
    while count1 < len(list1) and count2 < len(list2):
        if list1[count1] <= list2[count2]:
            final.append(list1[count1])
            count1 += 1
        else:
            final.append(list2[count2])
            count2 += 1
    if count1 == len(list1):
        for i in range(count2, len(list2)):
            final.append(list2[i])
    else:
        for i in range(count1, len(list1)):
            final.append(list1[i])
    return final

def merge_sort(nums):
    if len(nums) > 1:
        list1 = merge_sort(nums[:len(nums) // 2])
        list2 = merge_sort(nums[len(nums) // 2:])
        print(list1, "List1")
        print(list2, "list2")
        merged = merge(list1, list2)
        print(merged, "merge")
        return merged
    else:
        return nums

numbers = [2, 1, 3, 4, 6, 5, 8, 7]
print(merge_sort(numbers))

Upvotes: 0

Jo Bay
Jo Bay

Reputation: 106

Overall the structure is right. But there are just three smaller mistakes in this code.

The first is just a typo of list1 instead of list2. In the merge function, the while loop should have the condition while count1 < len(list1) and count2 < len(list2):

Next in the merge_sort function. list1 and list2 need to be updated while recursively calling merge_sort. Currently list1 and list2 always stay unsorted which is why the values are not moving around. (See updated below)

Finally, you forgot about the base case when len(nums)==1. In this case the list is already sorted because there is only one value. You still need to return that list though otherwise None is returned.

Merge sort should update to:

def merge_sort(nums):
    if len(nums) > 1:
        list1 = nums[:len(nums) // 2]
        list2 = nums[len(nums) // 2:]
        #need to update list1 and list2
        list1 = merge_sort(list1)
        list2 = merge_sort(list2)
        print(list1,"List1")
        print(list2,"list2")
        new_list = merge(list1,list2)
        print(new_list,"merge")
        return new_list
    #need a base condition
    else:
        return nums

Upvotes: 1

Karl Knechtel
Karl Knechtel

Reputation: 61526

When you make the recursive calls

    merge_sort(list1)
    merge_sort(list2)

, those calls produce new list objects (when the return statement is reached on those calls) which are then ignored (because you have done nothing with them). They do not affect the contents of list1 or list2, as seen by the current call. (Every time merge_sort is called, list1 and list2 can potentially refer to different values - calling recursively is not different from any other call in this regard.)

Instead of making the merge call on the unmodified list1 and list2, you need to use the return values from the recursive calls.

Separately: you are defining your recursive sort to create a new list. Therefore, in the case where len(nums) <= 1, you still need to return a new list. Otherwise, when the recursion reaches that step, it will return None implicitly, and you will get an exception when the previous call in the recursion tries to merge with that non-list value.

Upvotes: 1

filbranden
filbranden

Reputation: 8898

The problem is you have these two calls:

merge_sort(list1)
merge_sort(list2)

But you're assuming they're modifying list1 and list2 in place, which is not really the case... Use an assignment to store them back into their original variables:

list1 = merge_sort(list1)
list2 = merge_sort(list2)

You also have a small typo at the first while statement at the top, where count2 should be compared to the length of list2

while count1 < len(list1) and count2 < len(list2):

Upvotes: 0

Related Questions