To store what quicksort requires, O (logn) additional memory

Question

I mean I know Wiki says it used for call stack. But what exactly stores there? For what data of algorithm of sorting in a stack the memory is required?

QuickSort needs log n additional memory. For what? What stores there in this memory. What data. Is it for subarrays, for pivots ? What excacly Algorithm stores in additional memory? — Руслан Сударев, Feb 13 '18 at 03:09
The in-place version of quicksort has a space complexity of O(log n), even in the worst case, when it is carefully implemented using the following strategies:. In-place partitioning is used. This unstable partition requires O(1) space. After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(log n) space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack. This idea, as discussed above, was described by R. Sedgewick, and keeps the stack depth bounded by O(log n) — Mitch Wheat, Feb 13 '18 at 03:14

MBo · Accepted Answer · 2018-02-13T05:24:54.937

In the most of usual implementations stack stores starting and ending indexes for range that should be sorted later.

Recursive version:

                         int i = partition(a, l, r)
 here l,i =>              quicksort(a, l, i)
 and here i + 1, r =>     quicksort(a, i + 1, r)

Version with explicit stack (if-condition to provide lesser stack depth):

int i = partition(a, l, r)
    if (i - 1 > r - i) 
       s.push(l, i - 1)
       s.push(i + 1, r)
    else
       s.push(i + 1, r)
       s.push(l, i - 1)

To store what quicksort requires, O (logn) additional memory

1 Answers1