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

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?

2 answers

  • answered 2018-02-13 03:21 Mheni

    i think you might find your answer here
    this might not be it, but i believe the stack is used for function calls, and as the algorithm is recursive you would have lots of calls and you need the stack to save the state at each function call.
    hope this helps.

  • answered 2018-02-13 05:19 MBo

    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)