18

Quicksort is often described as an in situ (in-place) algorithm, despite the fact that it requires O(log n) stack space. So does in situ mean "requires less than O(n) additional space", or does stack space generally not count as space complexity (but why would that be the case?), or is Quicksort actually not an in situ algorithm?

Peter O.
  • 32,158
  • 14
  • 82
  • 96
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • 1
    This question has been asked before: http://cstheory.stackexchange.com/q/9563/6586. Basically, it is rather a flame bait with lots of contradictory arguments. – jpalecek Feb 01 '12 at 14:00
  • 2
    Note that this really depends on how you want *in-situ* to be defined. IF you are just comparing sorting algorithms it would be very nitpicky to not consider quicksort to be inplace but if you have a more formal definition in mind (hopefully with a reason) then it makes sense to stop ignoring the little O(log n) detail. – hugomg Feb 01 '12 at 14:02
  • This is just a special case of "O(log n) might as well be a largeish constant", isn't it? In principle Quicksort uses O(log n) additional space. In practice you generally implement it to take something like an array as a parameter. Arrays in most languages have a natural upper size limit based on the fixed-width type used for address and/or indices, and Quicksort only needs to store a couple of addresses at each of `log n` depths. So stack use is constant-bounded for almost any implementation of Quicksort you'd ever actually write and use, even though it isn't for the "ideal" version. – Steve Jessop Feb 01 '12 at 14:49
  • ... so all that remains is an argument about the appropriate definition of "in situ" - the properties of Quicksort are straightforward, but for example C's `qsort` has the property that any decent implementation of it has a fixed maximum stack use. – Steve Jessop Feb 01 '12 at 14:52
  • 1
    @Jason: Of course there is controversy, since definitions only have a meaning as far as they are useful. I think it is perfectly acceptable to consider quick-sort to be in-situ if all you are doing is comparing it with things like mergesort. The only reason one should go as far as giving a precise O(1) definition to in-situ is if you are defining a complexity class or doing something similarly formal. – hugomg Feb 01 '12 at 16:40
  • @Jesse What exactly do you mean by "fixed maximum stack use", O(1)? – fredoverflow Feb 01 '12 at 18:18
  • Interestingly enough `in situ` rhymes with Nico Lomuto's last name who invented [in-place partitioning scheme for quick sort](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme) – RBT Mar 10 '18 at 04:03

2 Answers2

20

is Quicksort actually not an in situ algorithm?

The standard implementation of it is not in situ. It's a horribly common misconception, but you as correctly note due to stack space consumption, that conception is wrong.

I say "standard implementation" of it because people have modified the algorithm to make it an O(1)-space algorithm. Here is one example: Quicksort without a stack.

Of course, consistent with the classic space-time tradeoff, such versions of quicksort are less performant than the standard implementation.

jason
  • 236,483
  • 35
  • 423
  • 525
9

Wikipedia offers the following definition:

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.

By this definition, the typical stack-based quicksort is clearly not an in situ algorithm.

In fact, the Wikipedia article explicitly discusses this:

An algorithm is sometimes informally called in-place as long as it overwrites its input with its output. In reality this is not sufficient (as the case of quicksort demonstrates) nor is it necessary; the output space may be constant, or may not even be counted, for example if the output is to a stream.

and

Quicksort is commonly described as an in-place algorithm, but is not in fact one. Most implementations require O(log n) space to support its divide and conquer recursion.

However, as pointed out by @Jason in his excellent answer, there appear to exist variants of quicksort that only require O(1) extra space. Any such alorithms would be considered in situ.

NPE
  • 486,780
  • 108
  • 951
  • 1,012