Python - quick sort - maximum recursion depth exceeded

Question

This is my code:

from random import randint

def quick_sort(sort_me):
    if len(sort_me) < 2:
        return sort_me

    pivot = sort_me[0]

    this = lower = upper = []

    for x in sort_me:
        if x < pivot:
            lower.append(x)
        elif x > pivot:
            upper.append(x)
        else:
            this.append(x)

    return quick_sort(lower) + this + quick_sort(upper)

And all I can see in terminal is this:

File "sorts.py", line 19, in quick_sort
  return quick_sort(lower) + this + quick_sort(upper)
RuntimeError: maximum recursion depth exceeded

I think something is wrong with this list but I don't know what. Help!

You could always take some tips from existing implementations such as - hetland.org/coding/python/quicksort.html — synthesizerpatel

user2357112 supports Monica user2357112 supports Monica · Accepted Answer · 2013-08-04T22:17:46

this = lower = upper = []

Assignment never creates copies in Python. This line doesn't create 3 lists; it creates 1 list, and makes this, lower, and upper all refer to that list. Make 3 lists.

this = []
lower = []
upper = []

Python - quick sort - maximum recursion depth exceeded

1 Answers