def combine2(left,right) :
l = r = 0
array = []
while l < len(left) and r < len(right) :
    if left[l] < right[r] :
        array  = [left[l]]
        l  = 1
    else :
        array  = [right[l]]
        r  = 1
    
while l < len(left) :
    array  = [left[l]]
    l  = 1

while r < len(right) :
    array  = [right[r]]
    r  = 1
return array
def merge_sort(array) :
     if len(array) == 1 :
         return
     k = len(array)//2
     left = array[k:]
     right = array[:k]
     merge_sort(left)
     merge_sort(right) 
     array = combine2(left,right)
     print array
merge_sort([8,7,6,5,4,3,2,1])

after dividing the original array, I merge them together using the combine2 function like above, which uses 2 indices i and j going through each element of the sorted array and fill the bigger element to the new empty merged array. The problem is that the array doesn't get updated to the new sorted array despite the fact that the combine2 function alone works just fine for 2 sorted arrays. Here's the output :

[1, 2]
[3, 4]      
[2, 1, 4, 3]
[5, 6]      
[7, 8]      
[6, 5, 8, 7]
[4, 3, 2, 1, 8, 7, 6, 5]

CodePudding user response：

You are doing a couple of things wrong:

a) First thing (I m not sure if its a typo): In the first while loop in the else condition, you should use r instead of l in array = [right[l]]. So it has to be array = [right[r]] And you really should use append instead like array.append(right[r]). array = [right[r]] keeps creating new copies! Very inefficient.

b) Second thing, the part array[k:] is actually the right part. Isn't it? after taking mid as k the part to its right is the right part. So array[:k] is left and array[k:] is right

c) Finally and more importantly, you are assuming that the array is sorted in place. But it is not. In the combine array you are returning a new array and it doesn't affect the original array. You should really combine the arrays returned by sorting left part and that obtained by sorting right part. So your merge_sort should return an array. Then you combine them.

Your modified merge_sort should look like:

def merge_sort(array):
    if len(array) == 1:
        return array
    k = len(array) // 2
    right = array[k:]
    left = array[:k]
    left = merge_sort(left)
    right = merge_sort(right)
    array = combine2(left, right)
    return array

CodePudding user response：

merge_sort does not modify the array in-place, it returns a modified array. So your two statements merge_sort(left) and merge_sort(right) aren't actually doing anything, because you throw away the results.

CodePudding user response：

There were minor issues with your script. The errors are written on the comments.

def combine2(left,right) :
    l = r = 0
    array = []

    # I used array.append(value) instead of array  = [value] because 
    # its more efficient.
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            array.append(left[l])
            l  = 1
        else:
            # There was an wrong index here. Fixed it.
            array.append(right[r])
            r  = 1
        
    while l < len(left):
        array.append(left[l])
        l  = 1

    while r < len(right):
        array.append(right[r])
        r  = 1

    return array

def merge_sort(array):
    if len(array) == 1:
        # This avoids errors with NoneType, and allows
        # the script to execute properly
        return array

    k = len(array)//2
    left = array[k:]
    right = array[:k]

    # You're always returning copies of each array.
    #
    # As you're not editing the same reference, you
    # should update the old array with the sorted
    # array whenever you call merge_sort.
    left = merge_sort(left)
    right = merge_sort(right) 
    array = combine2(left,right)
    print(array)

    # This is needed, as you're always returning a
    # copy of the array from combine2.
    return array

When executed, the output is:

[1, 2]
[1, 2, 3]
[4, 5]
[1, 2, 3, 4, 5]
[6, 7]
[6, 7, 8]
[9, 10]
[6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]