Knuth introduced the problem of sorting with a sequence
of stacks. Tarjan extended this idea to sorting with
acyclic networks of stacks (and queues), where items to
be sorted move from a source through the network to a
sink while they may be stored temporarily at nodes (the
stacks). Both characterized which permutations are
*sortable*; but complexity of sorting was not an
issue.

In contrast, given a complete, thus cyclic, network of
*k >= 2* stacks, any permutation is obviously
sortable. We ask how to do the sorting with a minimum
number of *shuffles*, i.e. moves in between
stacks. This is a natural algorithmic complement to the
structural questions asked by Knuth, Tarjan, and others.
It is the first time shuffles are considered in stack
sorting - despite their practical importance.

We show that it is NP-hard to approximate the minimum
number of shuffles within *O(n*^{1-e}) for
networks of *k >= 4* stacks, even when the problem
is restricted to complete networks, by relating stack
sorting to *MIN-k-PARTITION* on circle graphs (for
which we prove a stronger inapproximability result).
For complete networks, a simple merge sort algorithm
achieves an approximation ratio of *O(n log n)* for
*k >= 3*; however, closing the logarithmic gap to
our lower bound appears to be an intriguing open
question. Yet, on the positive side, we present a tight
approximation algorithm which computes a solution with a
linear approximation guarantee, using a resource
augmentation to *ak+1* stacks, given an
*a*-approximation algorithm for coloring circle
graphs.

When there are constraints as to which items may be
placed on top of each other, deciding about sortability
becomes non-trivial again. We show that this problem is
PSPACE-complete, for every fixed *k >= 3*.