Error "maximum recursion depth exceeded" while sorting a list with Quicksort

Question

I was trying to sort a almost sorted list of 100,000 of numbers with the Quick-sort algorithm, but I received this error:

Traceback (most recent call last):
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 48, in <module>
    quickSort(alist)
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 5, in quickSort
    quickSortHelper(alist,0,len(alist)-1)
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 12, in quickSortHelper
    quickSortHelper(alist,first,splitpoint-1)
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 12, in quickSortHelper
    quickSortHelper(alist,first,splitpoint-1)
.
.
(a bunch of the last line)
.
.
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 10, in quickSortHelper
    splitpoint = partition(alist,first,last)
  File "/Users/MacbookPro/Documents/Faculta/alg sortare pyth/quicksort.py", line 25, in partition
    while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
RuntimeError: maximum recursion depth exceeded in cmp

This is my code:

from timeit import default_timer as timer
import resource

start = timer()

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:    
       splitpoint = partition(alist,first,last)    
       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]    
   leftmark = first+1
   rightmark = last    
   done = False
   while not done:    
       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1    
       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1    
       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp    
   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp   
   return rightmark

with open('lista.txt', 'r') as f:
    long_string = f.readline()
    alist = long_string.split(',')
quickSort(alist)
f = open("quick.txt", "w")
print >>f,(alist)
print resource.getrusage(resource.RUSAGE_SELF).ru_maxrss / 1000
end = timer()
print(end - start)
f.close()
print 'Quick\n'

I tried before to sort the same list, after first shuffling it randomly, and then it worked.

Answer 1

Your choice of the pivot element (the leftmost in the range) will give a "bad" split when the input is already sorted. "Bad" in the sense that partition will return a rightmark that is equal to the value of first.

This means that in quickSortHelper a list of n values will be split into a list with zero elements (the first recursive call) and a list of n-1 values (the second recursive call). If the input is sorted already, this pattern will keep repeating at each recursive level. As a consequence, if your input has size 1000, then you will have a recursion depth of 1000. Python maintains a maximum recursion depth at which it will trigger the exception. For large sorted lists you will bump into this limit.

As a side note, in that case you also have a worst case running time of O(n²).

How to solve this?

You could configure Python to allow deeper recursion, with sys.setrecursionlimit. But this is not advisable, as it means you still use a lot of stack memory, and a don't get rid of the worst-case running time for input that is sorted.

A better way to solve this is to choose your pivot element randomly, somewhere between indexes first and last, and swap the value at that index with the leftmost value (or rightmost, but in your implementation it would be left). This will reduce the probability of getting the maximum recursion depth exceeded error to practically zero.

See also how Wikipedia refers to the very problem you bumped into (I stressed in bold):

Choice of pivot

In the very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot (as recommended by Sedgewick).

To implement a randomly selected pivot index, add these two lines to the very top of your partition function:

pivotmark = random.randint(first,last)
alist[first], alist[pivotmark] = alist[pivotmark], alist[first]

Of course, you need to import random.

This will solve the problem you bumped into. If you want to push performance further, you might have a look at several other solutions that exist, such as the ones mentioned in the Wikipedia article referenced above, and see how they perform on the input you are dealing with.

NB: See also how you can swap elements in one line...