병합 정렬 알고리즘 실패

Question

파이썬에서 병합 정렬 알고리즘을 작성했습니다. 그것은 10000 숫자까지 완벽하게 작동하지만 10000 후에 나에게 분할 결함 11을 준다. 무엇이 문제 일까? 그것에 대해 어떤 생각이든

def merge_count(arr): 
    if len(arr) < 2: 
     return (arr, 0) 
    m = int(len(arr)/2) 
    left, l_counter = merge_count(arr[:m]) 
    right, r_counter = merge_count(arr[m:]) 
    return merge(left, right, l_counter + r_counter) 


def merge(left, right, counter): 
    if len(left) * len(right) == 0: 
     return (left + right, counter) 
    if left[len(left) - 1] > right[len(right) - 1]: 
     val = left.pop(len(left) - 1) 
     counter += len(right) 
    else: 
     val = right.pop(len(right) - 1) 
    arr, counter = merge(left, right, counter) 

    return (arr + [val], counter) 

Answer 1

스택 오버플로가있는 것 같습니다. merge은 병합 할 목록 크기의 순서로 스택 공간을 사용합니다. 이는 파이썬이 처리 할 수있는 것보다 더 많은 방법입니다. 보통, 파이썬은 그 점에 도달하기 전에 RuntimeError으로 당신을 멈출 것입니다; 안전 한도를 지키려면 sys.setrecursionlimit을 사용했을 것입니다. setrecursionlimit을 사용을 중지하고 재귀를 사용하지 않으려면 merge을 다시 작성하십시오.