sortingstack

Is there an efficient way to sort data only using stacks?


Is there an efficient way to sort data only using stacks (more than 2 is allowed if this helps)?

I've seen two stack sorts, but those have time complexity O(n^2). I'm wondering if there is something with time complexity O(n log(n)) by using more than two stacks.


Solution

  • A merge sort can be implemented with 3 stacks in O(n log(n)). A simple implementation would move sorted runs alternately between two other stacks, then merge runs from those two other stacks back onto the original stack. The initial run size would be 1 element. The code would need to keep track of run sizes. If a small local array is allowed O(1) space complexity, then insertion sort could be used to create small runs of 16 to 64 elements. Each merge pass reads and writes each element twice, once to move sorted runs from original stack to the other two stacks, and once to merge the runs back. This can be improved by using polyphase merge sort, but it is not a stable sort (equal values may be reordered), and complicated, as the initial distribution needs to distribute the data to correlate to Fibonacci numbers, and runs have to alternate between ascending and descending, and may change in size during a merge phase, so that the final merge merges two descending runs onto a stack to end up with ascending data in the final stack.

    https://en.wikipedia.org/wiki/Polyphase_merge_sort

    The number of elements moved can be decreased by using more stacks. For the simple method, using 5 stacks with a 4 way merge: 0.5 x moves, but 1.5 x compares. Polyphase merge sort would need 4 stacks to do a 4 way merge, and it would be more complicated than 3 stack polyphase merge sort.

    Example C++ code for 3 stack polyphase merge sort. Note that it swaps stack containers, so the sorted data can end up in a different instance of stack.

    typedef unsigned long long uint64_t;
    
    static size_t fibtbl[48] =
        {        0,         1,         1,         2,         3,         5,
                 8,        13,        21,        34,        55,        89,
               144,       233,       377,       610,       987,      1597,
              2584,      4181,      6765,     10946,     17711,     28657,
             46368,     75025,    121393,    196418,    317811,    514229,
            832040,   1346269,   2178309,   3524578,   5702887,   9227465,
          14930352,  24157817,  39088169,  63245986, 102334155, 165580141,
         267914296, 433494437, 701408733,1134903170,1836311903,2971215073};
         
    // binary search: return index of largest fib() <= n
    size_t flfib(size_t n)
    {
    size_t lo = 0;
    size_t hi = sizeof(fibtbl)/sizeof(fibtbl[0]);
        while((hi - lo) > 1){
            size_t i = (lo + hi)/2;
            if(n < fibtbl[i]){
                hi = i;
                continue;
            }
            if(n > fibtbl[i]){
                lo = i;
                continue;
            }
            return i;
        }
        return lo;
    }
    
    // poly phase merge sort array using 3 stacks, a is source
    void ppmrg3(std::stack <uint64_t> &a)
    {
    size_t n = a.size();
        if(n < 2)
            return;
    std::stack <uint64_t> b;
    std::stack <uint64_t> c;
    bool dsf;                               // == 1 if descending sequence
    size_t ars = 1;                         // init run sizes
    size_t brs = 1;
    size_t asc = 0;                         // no size change
    size_t bsc = 0;
    size_t csc = 0;
    size_t scv = (size_t)0-(size_t)1;       // size change value
    
    
        {                                   // block for local variable scope
            size_t f = flfib(n);            // fibtbl[f+1] > n >= fibtbl[f]
            dsf = ((f%3) == 0);             // init compare flag
            if(fibtbl[f] == n){             // if exact fibonacci size, move to b
                for(size_t i = 0; i < fibtbl[f-1]; i++)
                    b.push(a.top()), a.pop();
            }
            else {                        // else move to b, c
             // update compare flag
                dsf ^= (n - fibtbl[f]) & 1;
                // i = excess run count
                size_t i = a.size() - fibtbl[f];
                // j = dummy run count
                size_t j = fibtbl[f + 1] - a.size();
                // move excess elements to b
                do {
                    b.push(a.top()), a.pop();
                } while (0 != --i);
                // move dummy count elements to c
                do {
                    c.push(a.top()), a.pop();
                } while (0 != --j);
                csc = c.size();
            }
        }                                   // end local variable block
        while(1){                           // setup to merge pair of runs
            if(asc == a.size()){            // check for size count change
                ars += scv;                 //   (due to dummy run size == 0)
                scv = 0-scv;
                asc = 0;
                csc = c.size();
            }
            if(bsc == b.size()){
                brs += scv;
                scv = 0-scv;
                bsc = 0;
                csc = c.size();
            }
            size_t arc = ars;               // init run counters
            size_t brc = brs;
            while(1){                       // merging pair of runs
                if(dsf ^ (a.top() <= b.top())){
                    c.push(a.top());        // move a to c
                    a.pop();
                    if(--arc != 0)          // if not end a
                        continue;           //   continue back to compare
                    do{                     // else move rest of b run to c
                        c.push(b.top());
                        b.pop();
                    }while(0 != --brc);
                    break;                  //   and break
                } else {
                    c.push(b.top());        // move b to c
                    b.pop();
                    if(0 != --brc)          // if not end b
                        continue;           //   continue back to compare
                    do{                     // else move rest of a run to c
                        c.push(a.top());
                        a.pop();
                    }while(0 != --arc);
                    break;                  //   and break
                }
            }                               // end merge pair of runs
            dsf ^= 1;                       // toggle compare flag
            if(b.empty()){                  // if end b
                if(a.empty())               //   if end a, done
                    break;
                std::swap(b, c);            //   swap b, c
                brs += ars;
                if (0 == asc)
                    bsc = csc;
            } else {                        // else not end b
                if(!a.empty())              //   if not end a
                    continue;               //     continue back to setup next merge
                std::swap(a, c);            //   swap a, c
                ars += brs;
                if (0 == bsc)
                    asc = csc;
            }
        }
        std::swap(a, c);                    // put sorted stack in a
    }