Recursion in Python 3

user_10394279 0
Viewed 110

I was trying to do merge sort in a different way (instead of those available in texts or so..), now I have a successful merge algorithm, but the thing is that when I recursively call on half lists, the merged thing doesn't get updated. Help me with variable life in the recursion.

The output of the below-given code is: - 

[9, 5]
After merging [5, 9]
[12, 4]
After merging [4, 12]
[9, 5, 12, 4] #it should be (the updated one i.e  [5, 9, 4, 12])
After merging [5, 9, 12, 4]
[6, 8]
After merging [6, 8]
[45, 2]
After merging [2, 45]
[6, 8, 45, 2]
After merging [6, 8, 45, 2]
[9, 5, 12, 4, 6, 8, 45, 2]
After merging [4, 5, 6, 8, 9, 12, 45, 2]
[9, 5, 12, 4, 6, 8, 45, 2]

def merge(arr1, arr2):
"""
Input is two sorted lists
Output is a single merged list
"""
        for i in arr1:
            for j in list(range(len(arr2))):
                if i<arr2[j]:
                    arr2.append(arr2[-1])
                    for count in list(range(len(arr2)-1, j, -1)):
                        arr2[count] = arr2[count-1]
                    arr2[j] = i
                    break
                if j == len(arr2)-1:
                    arr2.append(i)
        return arr2
    def mergeSort(arr):
        if len(arr) !=1:
            mergeSort(arr[:len(arr)//2])
            mergeSort(arr[len(arr)//2:])
            print(arr)
            arr = merge(arr[:len(arr)//2],arr[len(arr)//2:])
            print("After merging", arr)

        else:
            return arr
    a = [9,5,12, 4, 6, 8,45, 2]
    mergeSort(a)
    print(a)
mergesort recursion python-3.x python
2 Answers

You should make mergeSort return the merged list, and the caller should output the returning value of mergeSort instead:

def merge(arr1, arr2):
    merged = []
    while arr1 and arr2:
        if arr1[0] > arr2[0]:
            arr1, arr2 = arr2, arr1
        merged.append(arr1.pop(0))
    merged.extend(arr1 or arr2)
    return merged
def mergeSort(arr):
    if len(arr) <= 1:
        return arr
    return merge(mergeSort(arr[:len(arr)//2]), mergeSort(arr[len(arr)//2:]))
a = [9, 5, 12, 4, 6, 8, 45, 2]
print(mergeSort(a))
user_68909120

I only make sooo little changes so the code remain yours with your effort, you were so close, look:

The thing is, after reviewing your code, you have to pass the two halves to the merge method, and also check if it is empty. Besides, is considerably better to return the results and not make changes in place-

def merge(arr1, arr2):
        for i in arr1:
            for j in list(range(len(arr2))):
                if i<arr2[j]:
                    arr2.append(arr2[-1])
                    for count in list(range(len(arr2)-1, j, -1)):
                        arr2[count] = arr2[count-1]
                    arr2[j] = i
                    break
                if j == len(arr2)-1:
                    arr2.append(i)
        return arr2
def mergeSort(arr):
    if len(arr) !=1 and len(arr):
        ary1 = mergeSort(arr[:len(arr)//2])
        ary2 = mergeSort(arr[len(arr)//2:])
        print(arr)
        ary3 = merge(ary1,ary2)
        print("After merging", ary3)
        return ary3
    else:
        return arr
a = [9,5,12, 4, 6, 8,45, 2]

print(mergeSort(a))

the output

[9, 5]
After merging [5, 9]
[12, 4]
After merging [4, 12]
[9, 5, 12, 4]
After merging [4, 5, 9, 12]
[6, 8]
After merging [6, 8]
[45, 2]
After merging [2, 45]
[6, 8, 45, 2]
After merging [2, 6, 8, 45]
[9, 5, 12, 4, 6, 8, 45, 2]
After merging [2, 4, 5, 6, 8, 9, 12, 45]
[2, 4, 5, 6, 8, 9, 12, 45]
user_71280340
Related