4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Dec 19 '14 at 7:47
10
$\begingroup$

Quicksort: For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity.

Mergesort: Since mergesort also calls itself on the order of log(n) times, why the O(n) space requirement? The extra space comes from the merge operation. Most implementations of merge use an auxiliary array with length equal to the length of the merged result, since in-place merges are very complicated. In other words, to merge two sorted arrays of length n/2, most merges will use an auxiliary array of length n. The final step of mergesort does exactly this merge, hence the O(n) space requirement.

To see exactly how the auxiliary array is used, check out this implementation of merge.

Summary: The key difference between the two lies in the space requirement of the operation performed at each recursive step. The partition step used in quicksort is an in-place operation, while merging usually requires an auxiliary array.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.