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

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