-1

I want to code merge sort in Python 3.

Here is my code:

import math

def Merge(array,start,mid,end):
    n1 = mid - start +1
    n2 = end - mid
    i = 0
    j = 0
    left = [None] * n1
    right = [None] * n2
    inv = 0
    for i in range(0,n1):
        left[i] = array[start + i - 1]
    for j in range(0,n2):
        right[j] = array[mid + j]

    left.append(math.inf)
    right.append(math.inf)
    new_list = []
    for k in range(0,end):
        if left[i] <= right[j]:
            array[k] = left[i]
            i+=1
        elif left[i] > right[j]:
            array[k] = right[j]
            j+=1

def MergeSort(array,start,end):
    if len(array) <= 1:
        return array
    mid = math.ceil((start + end)/2)
    MergeSort(array,start,mid)
    MergeSort(array,mid+start,end)
    Merge(array,start,mid,end)


stuff = [1, -5, 17, 32, 6] 
MergeSort(stuff, 0, len(stuff))
print(stuff)

I tested first function(Merge) it works as it should. But I have a problem with the recursion. I cannot figure out where is the problem. The error is "maximum recursion depth exceeded in comparison".

Prune
  • 76,765
  • 14
  • 60
  • 81
Daniel Yefimov
  • 860
  • 1
  • 10
  • 24
  • [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. Your posted code defines two functions and quits without any calls at all. – Prune Aug 14 '18 at 17:44
  • Insert this line in your MergeSort function (as the first line) and see for yourself whats going on `print("Start %i End %i" % (start,end))` . This has nothing to do with recursion limit – Some Guy Aug 14 '18 at 17:49
  • Seems `for k in range(0,end): ` should be `for k in range(start,end):` – MBo Aug 14 '18 at 17:52

1 Answers1

3

You have no functional exit from MergeSort. The length of the list never changes, as you pass the entire list on every call. If you start with 5 elements in the list, then len(array) is always 5. As a result, you get down to the left-hand base item (one element) and continue to hammer on that one element forever.

Try checking the bounds, such as

if end - start <= 1:

This will at least get you to the next execution problems.

See this lovely debug blog for help. If nothing else, learn to put in useful print statements to trace data and control flow.

Prune
  • 76,765
  • 14
  • 60
  • 81