有没有一种仅使用堆栈来对数据进行排序的有效方法？

合并排序可以用 3 个堆栈在 O(n log(n)) 内实现。一个简单的实现是交替地在两个堆栈之间移动已排序的运行，然后将这两个堆栈中的运行合并回原始堆栈。初始运行大小为 1 个元素。代码需要跟踪运行大小。如果允许小型本地数组具有 O(1) 空间复杂度，则可以使用插入排序来创建 16 到 64 个元素的小运行。每次合并过程读取和写入每个元素两次，一次将已排序的运行从原始堆栈移动到其他两个堆栈，一次将运行合并回去。这可以通过使用多相合并排序来改进，但它很复杂，因为初始分布最终的运行大小与斐波那契数相关，并且运行必须在升序和降序之间交替，因此最终合并将两个降序运行合并到一个堆栈上，最终堆栈中的数据为升序。

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

通过使用更多堆栈可以减少移动元素的数量。对于简单方法，使用 5 个堆栈进行 4 路合并：0.5 次移动，但 1.5 次比较。多相合并排序需要 4 个堆栈才能进行 4 路合并，并且它比 3 个堆栈多相合并排序更复杂。

3 堆栈多相归并排序的示例 C++ 代码。请注意，它交换堆栈容器，因此排序后的数据可能最终位于不同的堆栈实例中。

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
}