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

Joey Franklin picture Joey Franklin · Sep 24, 2012 · Viewed 39.3k times · Source

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;
}

Answer

rolve picture rolve · Sep 24, 2012

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.