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?

Answer 1

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).

---

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