The call stack size of quick sort

Question

I read this answer and found an implementation of Quicksort here. It's still unclear to me why Quicksort requires O(log n) extra space.

I understand what a call stack is. I applied the implementation stated above to an array of random numbers and saw n - 1 calls of quickSort.

public static void main(String[] args) {
        Random random = new Random();
        int num = 8;
        int[] array = new int[num];
        for (int i = 0; i < num; i++) {
            array[i] = random.nextInt(100);
        }
        System.out.println(Arrays.toString(array));

        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    static int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }

        return i;
    }

    static void quickSort(int arr[], int left, int right) {
        System.out.println("quickSort. left = " + left + " right = " + right);
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }

The output I saw:

[83, 65, 68, 91, 43, 45, 58, 82]

quickSort. left = 0 right = 7

quickSort. left = 0 right = 6

quickSort. left = 0 right = 4

quickSort. left = 0 right = 3

quickSort. left = 0 right = 2

quickSort. left = 0 right = 1

quickSort. left = 5 right = 6

[43, 45, 58, 65, 68, 82, 83, 91]

It makes that 7 (n -1) calls. So why does quickSort require O(log n) space for its call stack if the number of calls depends on n, not log n?

possible duplicate of [Intuitive explanation for why QuickSort is n log n?](http://stackoverflow.com/questions/10425506/intuitive-explanation-for-why-quicksort-is-n-log-n) — David W, Jun 09 '15 at 19:38
@DavidW, the answer you mention is about the time complexity. But my question is about the space complexity — Maksim Dmitriev, Jun 09 '15 at 19:54
I thought the space complexity of Quicksort was, in fact, O(n) — David W, Jun 09 '15 at 20:01
And my apologies for misreading the post. You're right - it's not about time complexity. I rescinded the close/dup vote. — David W, Jun 09 '15 at 20:02

Maksim Dmitriev · Answer 1 · 2015-06-12T21:08:38.337

I think I understand why the stack size of Quicksort is O(n) in the worst case.

One part of the array (suppose left) to be sorted consists of one element, and the other part (right) consists of n - 1 elements. The size of the left part is always 1, and the size of the right part decrements by 1 every time.

Thus, we initially call Quicksort and then call it n - 1 times for the right part recursively. So extra space for the call stack is O(n). And since the partitioning procedure takes O(n) for every recursive call, the time complexity is O(n2).

As for the average case analysis, now I don't know how to prove O(n * log n) for the time complexity and O(log n) for extra space. But I know that if I divide the input array into two almost equal parts, I'll call Quicksort (log n) / 2 times for the left part. And the right part is sorted using tail recursion which doesn't add to the call stack.

https://en.wikipedia.org/wiki/Quicksort

So extra space needed for Quicksort is O (log n) in this case. The constant factor 1/2 is left out.

Since the partitioning routine is n, the time complexity is O(n * log n).

enter image description here

Please correct me if my assumptions are wrong. I'm ready to read and accept your answer.

The call stack size of quick sort

1 Answers1