At 1,000,000 items you have 20 (in the best case, at least) levels of recursion....

fp on July 11, 2008 | parent | context | favorite | on: Three Beautiful Quicksorts

At 1,000,000 items you have 20 (in the best case, at least) levels of recursion. I can assure you, your stack space is more than sufficient for that.

Also, you only have to push a handful of pointers to the stack, which doesn't seem to be expensive to me.