Is Quicksort in-place or not?

Intro to Algorithms from MIT Press qualifies QuickSort as in-place – it sorts the elements within the array with at most a constant amount of them outside the array at any given time.

At the end of the day, people will always have differing opinions (is Top-Down Memoization considered Dynamic Programming? Not to some “classical” folks), side with who you trust the most. I trust the editors and the authors at MIT Press (along with my professor, who qualifies it as in-place).

Typically, the problem with QuickSort is not that it doesn’t sort in-place, but that it is not stable – satellite data is not kept in order.

Edit

Kuroi’s point highlights part of this argument I think is very important.

Many argue that it requires O(log(n)) extra memory for recursive calls and the data is leaked in the form of the indices on the stack, however this is negligible for very large sizes of N (log(1,000,000,000) =~ 30) and it ignores the fact that typically moving data on the heap takes much, much longer, when size(data) >> size(index).

The indices of the data are not the elements themselves – so the elements of the data are not stored outside the array, other than a constant amount of them (in each call).

Leave a Comment