python merge sort implementation error: maximum recursion depth exceeded-CodePudding

Here is a simple merge sort algorithm I tried to implement in python. I tried to do this without using left and right parameters which are found elsewhere, only using slices.

from math import floor


def merge(A, B):
    """Mearges the two sorted lists A and B"""
    merged = []
    i, j = 0, 0
    while i < len(A) and j < len(B):
        if A[i] <= B[j]:
            merged.append(A[i])
            i  = 1
        else:
            merged.append(B[j])
            j  = 1
    
    if j == len(B):
        merged.extend(A[i:])
    elif i == len(A):
        merged.extend(B[j:])
    
    return merged

def merge_sort(A):
    if len(A) == 1:
        return A
    
    m = floor(len(A) / 2)
    half1 = A[0:m]    
    half2 = A[m:]
    A = merge_sort(half1)
    B = merge_sort(half2)
    R = merge(A, B)
    return R



def main():
    C = [6, 7, 2]
    print(merge_sort(C))
    exit()

if __name__ == "__main__":
    main()

And it worked fine. But when I tried

A = merge_sort(A[0:m])
B = merge_sort(A[m:])

instead of using the variables half1 and half2 in merge_sort function, I got this:

Traceback (most recent call last):
  File "/home/aayush/PyProgs/mrg_sort.py", line 44, in <module>
    main()
  File "/home/aayush/PyProgs/mrg_sort.py", line 40, in main
    print(merge_sort(C))
  File "/home/aayush/PyProgs/mrg_sort.py", line 32, in merge_sort
    B = merge_sort(A[m:])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  File "/home/aayush/PyProgs/mrg_sort.py", line 31, in merge_sort
    A = merge_sort(A[0:m])
  [Previous line repeated 993 more times]
  File "/home/aayush/PyProgs/mrg_sort.py", line 25, in merge_sort
    if len(A) == 1:
RecursionError: maximum recursion depth exceeded while calling a Python object

Please tell me what I have done wrong.

CodePudding user response：

you just need to keep check of variable naming since here A is updated and you are using that list data not the orignal one

def merge_sort(A):
    if len(A) == 1:
        return A
    
    m = floor(len(A) / 2)
    c = merge_sort(A[0:m])
    B = merge_sort(A[m:])
    R = merge(c, B)
    return R

CodePudding user response：

Have you try with smaller data ?

Try :

import sys sys.setrecursionlimit(10000)

Then retry If algorithm not ended, you have an infinite loop