# Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

I've searched on internet and everybody said it's stack space needed on recursion. I know log(n) extra space for quick sort happened when use in place, but still I don't get it. Anybody can explain intuitively why quick sort need log(n) extra space and mergesort need n? Thanks.

• The claim is wrong; both need linear space in the worst case. So is this about average case? Then, there still is no definite answer as it depends on the details. Which implementation do you consider? Are you sorting arrays or lists? – Raphael Dec 19 '14 at 7:47

• Why recursion depth estimated as $O(\log N)$? – Mr. Newman Oct 7 '17 at 17:31