Quicksort has a space complexity of O(log(n)) in the average case. This arises from the recursive function calls and the partitioning process. It can be O(n) due to an unbalanced partitioning leading to a deep recursion stack in the worst case.

for each (unsorted) partition

set first element as pivot

storeIndex = pivotIndex+1

for i = pivotIndex+1 to rightmostIndex

if ((a[i] < a[pivot]) or (equal but 50% lucky))

swap(i, storeIndex); ++storeIndex

swap(pivot, storeIndex-1)