Why does QuickSort use O(log(n)) extra space?

Question

I have implemented the below quicksort algorithm. Online I've read that it has a space requirement of O(log(n)). Why is this the case? I'm not creating any extra data structures.

Is it because my recursion will use some extra space on the stack? If this is the case, is it possible to do it with less memory by not having it be recursive (instead making it iterative)?

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on right
        while (array[left] < pivot)
            left++;

        //Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        //Swap elements and move left and right indices
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

Solution 1

Correct, the extra space are the log(n) stack frames. From the Wikipedia article of Quicksort:

There is a more complex version which [...] can achieve the complete sort using O(log n) space (not counting the input) on average (for the call stack).

While you could implement quicksort iteratively (i.e., using a loop instead of recursion), you would then need to maintain an auxiliary stack, because Quicksort has two recursive calls and not just one.

Finally, as other answers have pointed out, O(log(n)) is for pretty much all practical applications very, very small. Every constant factor, like the overhead of your data structure, will have a greater impact on memory usage.

Solution 2

To get rid of the recursive call you would have to use a stack data structure in your code, and it would still occupy log(n) space.

Solution 3

If you read further in the Wikipedia article, you will find a more thorough discussion of space complexity. In particular, they write:

Quicksort with in-place and unstable partitioning uses only constant additional space before making any recursive call. Quicksort must store a constant amount of information for each nested recursive call. Since the best case makes at most O(log n) nested recursive calls, it uses O(log n) space. However, without Sedgewick's trick to limit the recursive calls, in the worst case quicksort could make O(n) nested recursive calls and need O(n) auxiliary space.

Practically speaking, O(log n) memory is nothing. For instance, if you were to sort 1 billion ints, storing them would require 4 GB, but the stack would only require about 30 stack frames, at something like 40 bytes, so about 1200 Bytes in total.

Solution 4

Sorry for reviving this old question, but I just found an entirely different (but slightly silly) answer to your question, on planetmath.org:

Any sorting algorithm that operates on a contiguous array requires O⁢(log ⁡n) extra space, since this is the number of bite [sic] required to represent an index into the array.

Solution 5

Yes, it is because of the stack frames, and yes, it may be possible to convert it to an iterative algorithm by doing something very clever (although nothing is immediately coming to me). But why? O(log(n)) space is almost nothing. For reference, even if you have an array of the maximum size allowed by Java, thats 2^31 elements, which is about 8 GB. Quicksort would require 31 stack frames. Ballpark, maybe 100 bytes per frame? So 3 KB total, which is nothing compared to the memory for the actual array.

In reality, almost any time something is O(log(n)), it's pretty much the same as constant.

View more solutions

Comments

[rolve]

You're right, log(n) is indeed very small but I wouldn't go as far as saying it's "pretty much the same as constant". ;-) Also, the maximal stack size is typically much smaller than the maximal heap size too.

[rici]

@rolve, for a given real-world machine, it's effectively constant since the maximum stack depth cannot be more than log2 of the number of elements in the sequence, as Joe K (almost) says. (Although, Joe K, you do know that 31 * 100 bytes is 3.1 Kb, not 300Kb. Typo, no?) Say you have a 64-bit architecture and a Google-sized budget, maybe you could push it to 50 stack frames, but that's still going to be less than 8K, which "might as well be constant." However, theoretically it's O(log n). Also, you can only achieve this by recursing first on the smaller partition. (Proof left to readers.)

[Tony]

Recently found an interesting note, that you can make quicksort to use only O(log(N)) space even in the case if it runs in O(N^2) time (which happens when, for example, pivot is always the minimum element etc. - just reminding worst case is O(N^2) for quicksort). When you go recursively for 'left' and 'right' part after partitioning, you can rearrange calls to make smaller part to go recursively and optimize the other part as tail recursive call. In that way recursion is needed for at max half the size of original collection => always O(log N) recursive calls.

[avmohan]

It is of course possible to make an iterative version of quick sort using an auxiliary stack.

[joe_04_04]

I'm not entirely sure that using the statement "making it iterative is not possible because it is not tail recursive" is a bit inaccurate. You can convert non-tail recursive functions into tail-recursive functions, then into iterative versions.

[rolve]

@joe_04_04 Thanks for the comment. You're right, being tail recursive or not is a property of a function, not of an algorithm. I updated my answer.