Why is Quicksort described as “in-place” if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

Question

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.

Answer 1

This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented.

In an in-place implementation, instead the sort function is not called recursively on newly constructed arrays that become smaller and smaller, but on bounds that become closer and closer.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Beware of this code, I have only typed it, not proved it. Any off-by-one errors are yours to fix. Real-world implementations would use a different algorithm for small sizes but this doesn't affect asymptotic behavior. Real-world implementations would choose a better pivot but I won't get into that here as it doesn't really for this question.)

The Wikipedia page presents both a non-in-place and an in-place version of the algorithm.

Quicksort as written here requires $O(d) + s$ extra storage, where $d$ is the depth of the recursion (which depends on the pivot quality) and $s$ is the element size. The stack size requirement can be improved: there are two recursive calls, and we can make the second one a tail call (which consumes no stack). If we always do the recursive call on the smaller half first, then the maximum stack size for array lengths up to $n$ satisfies $\hat S(n) \le \hat S(m)$ with $m \le n/2 \le \hat S(n/2)$, so $\hat S(n) \le \lg_2(n) \hat S(1)$. Thus we can achieve $O(\log n) + s$ extra storage requirement, regardless of the pivot choice.

There are plenty of other sorting algorithms that can be implemented in-place, including insertion sort, selection sort and heap sort. The simple form of merge sort isn't in-place, but there is a more sophisticated variant which is.

_{Thanks to Aryabhata for pointing out that Quicksort can always be done in $\lg(n)$ stack and that there is a variant of merge sort with both $O(1)$ additional storage and $O(n \log(n))$ runtime.}

Answer 2

In addition to Gilles' answer, you can also make Quicksort in-place with your code, if you use linked lists instead of arrays. Just make sure to remove the element from the original list, when appending them to one of the smaller lists.

The following pseudocode assumes/guarantees:

• The first entry in each list (in the following called the head) does not stare an element and allows to keep pointers to the list intact on modifications. new list creates a list consisting of a head with NIL next-pointer.
• sort takes a pointer to a head and returns a pointer to the last element of the sorted list. The pointer given as the argument is also the head of the sorted list.
• The memory location of each element and of the list head remains the same.

.

sort(list):
    less_cur = less = new list
    equal_cur = equal = new list
    greater_cur = greater = new list
    if list.next != NIL:
        cur = list.next
        pivot = cur.value
        while cur != NIL:
            list.next = cur.next
            if cur.value < pivot:
                less_cur.next = cur
                less_cur = less_cur.next
            if cur.value == pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            if cur.value > pivot:
                equal_cur.next = cur
                equal_cur = equal_cur.next
            cur = cur.next
        less_cur.next = greater_cur.next = NIL
        less_last = sort(less) 
        list.next = less.next
        less_last.next = equal
        greater_last = sort(greater)
        equal_cur.next = greater.next
        return greater_last
    else:
        return list

While there is some optimization possible from the above code, this implementation has a greater memory overhead than the array based implementation in Gilles' answer. Additionally it suffers in practice from the problem that linked lists typically are less localized and thus induce a greater number of cache misses than maintaining the same data in an array.

However, this implementation is of advantage, if you have to maintain pointers to the elements through sorting. It is also good to be aware of it, if you are storing your data in a linked list for reasons unrelated to sorting. (If in-place-ness of sorting is of concern, converting between list and array is likely out of question.)