以下のクイックソートアルゴリズムを実装しました。オンラインで、O（log（n））のスペース要件があることを読みました。これはなぜですか？余分なデータ構造を作成していません。
私の再帰がスタック上の余分なスペースを使用するためですか? この場合、再帰的ではなく（反復的にするのではなく）少ないメモリでそれを行うことは可能ですか？
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;
}