Quicksort is described as "in-place" but using an implementation such as:
def sort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
return sort(less) + equal + sort(greater)
else:
return array
You have to create a copy of the list for each recursion. By the first return, in memory we have:
- array
- greater+equal+less
Then by the second recursion across all sub-lists we have:
- array
- greater, equal, less from first recursion
- greater+equal+less from less1, greater+equal+less from greater1
etc...
Is this just badly written code or am I correct in thinking that for a big list, you actually have to have, proportionally, a fair amount of extra space to store thse?
When I think of something that is "in-place", I think of bubble sort, which simply swaps elements in the list like: http://en.wikipedia.org/wiki/File:Bubble-sort-example-300px.gif
BubbleSort only requires 1 extra variable to store a potentially swapped element.