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.
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
}