Python quick sort- recursive error running on terminal

Question

would anyone know why I am getting the following recursive error on my quicksort? Not sure why I'm getting a "RecursionError: maximum recursion depth exceeded in comparison". I've asked others and they said that my recursion should not be exceeding:

Here is the code:

def merge(array, low, mid, high):

i,j,k = low,mid+1,low
leftarray = array[low:mid+1]
rightarray = array[mid+1:high+1]

temp= [0]*high

while i<=mid and j<=high:

    if array[i]<array[j]:
        temp[k] = array[i]
        i+=1
    else:
        temp[k] = array[j]
        j+=1
    k+=1

if i>mid:
    temp[k:high+1] = array[j:high+1]
else:
    temp[k:high+1] = array[i:mid+1]  

array[low:high+1] = temp[low:high+1]

And the error

(base) b98-aruba1-guest-10-110-7-206:desktop ericadamian$ python Quicksort1.py
RecursionError: maximum recursion depth exceeded in comparison
(base) b98-aruba1-guest-10-110-7-206:desktop ericadamian$

What is the terminating condition for your recursive function? — brokenfoot
Quicksort1(array, index, low, index + 1) This is an infinite recursion. It will call itself with the same low and index values. — khelwood
Possible duplicate of stackoverflow.com/questions/53786145/recursionerror-in-python — ivan_pozdeev
Maybe should be -1 instead of +1 in the first recursive call - your high value is just getting bigger and bigger each time, so the if statement will always be True — Simon Crane
Please don't make more work for others by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license, for SE to distribute the content (i.e. regardless of your future choices). By SE policy, the non-vandalized version is distributed. Thus, any vandalism will be reverted. Please see: How does deleting work? …. If permitted to delete, there's a "delete" button below the post, on the left, but it's only in browsers, not the mobile app. — Makyen

rcgldr rcgldr · Accepted Answer · 2019-10-01T01:04:28

Fixes noted in comments.

def Quicksort1(array, low, high):               #fix

    if high > low:
        index = Partition(array, low, high)     #fix
        Quicksort1(array, low, index - 1)       #fix
        Quicksort1(array, index + 1, high)      #fix

def Partition(array, low, high):                #fix

    firstitem = array[low]
    j = low
    for i in range(low+1, high+1):              #fix
        if array[i] < firstitem:
            j+=1
            array[j], array[i] = array[i], array[j]
    index = j
    array[low], array[index] = array[index], array[low]     
    return index                                #fix

array = [10, 3, 4, 8, 1, 7]
Quicksort1(array, 0, len(array)-1)              #fix
for j in range(len(array)):                     #fix
    print ("%d" %array[j])                      #fix

Python quick sort- recursive error running on terminal

1 Answers