A quicksort can be defined as the following:

$1$ Function Quicksort$($A$,$ lo$,$ hi$)$

$2$ if lo $<$ hi

$3$ i $=$ Split$($A$,$ lo$,$ hi$)$

$4$ Quicksort$($A$,$ lo$,$ i$-1)$

$5$ Quicksort$($A$,$ i$+1,$ hi$)$

Recursion does the bookkeeping for this. If the array A has N elements, how deep can the recursive stack get? That is$,$ how many instances of quicksort can be active at once?

sqrt$($N$)$

log$2$N

N

Depends on the contents of the array