# Sorting a large number of unknown items with multiple stacks

Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it.

Problem:

I have a single stack already populated with several thousands of unknown items. (Not completely unique items, maybe 300 different values. So it's a stack with plenty of duplicates shuffled together in a random order.) I want to sort these items by moving them between a limited number of other stacks. (Maybe between 10-30 stacks at most.) An algorithm with less moves is ideal.

Limitations:

• The initial stack is full of unknown values (except for the top item).
• I can read the top item in a stack.
• I can move the top item of a stack directly to the top of another stack.
• I can check if a stack is empty.
• I can remember and store all the items I have read and moved.

Based on the above limitations, all the items need to be moved once to another stack just so they can be read/scanned. Then I would know where and what everything is.

Once this is done I can do the real sorting. (This is the part I mainly need help with.) After I've read and moved all the items once, I can then calculate and queue up all the stack moves needed to actually sort the items.

Presorting and optimizing:

It might be too early to think about this, but I can potentially do some pre-sorting onto different stacks as the items are first read and moved.

I do have a overall idea about the distribution of all the items. For instance, if the items were sorted alphabetically, I might know that items values starting with "S" are five times more common then items that start with "V" and that "S" is also twice as common as items starting with "A". Is knowing this even useful here?

I'm not sure if this would be helpful for pre-sorting but in some instances I might also know all the possible values of the items. So I could calculate if the value of an item is "odd" or "even". Even other similar calculations can be done (like the remainder of a larger modulos operation). Maybe separating the items into "odd" or "even" stacks would make it easier to weave into the final sorted stacks. I'm just speculating here, since I haven't run any tests yet.

Desired Result:

Items don't need to be sorted back into a single stack, it would probably actually be more ideal if they were moved into several smaller stacks of somewhat equal size. For example, I might end with alphabetically sorted stacks as such: A-D, D-K, K-R, R-S, S-Z.

What kind of algorithms would be best given these limitations? Pseudo code?

• can you describe your actual problem and use-case? they way you describe it, it sound like you should use Linked-Lists instead of proper stacks, and then just sort the lists. Maybe a simple merge-sort? or even a radix or bucket sort....
– AK_
May 2, 2015 at 10:10
• Aside from the initial stack which is more of a black box, I think you are right, I probably do want to store everything else in lists, so I can remember the placement of everything. However I'm still stuck with the above limitations for the operations on how I'm allowed to sort the lists, as they are physical limitations. May 2, 2015 at 15:39
• It seems you're solving en.wikipedia.org/wiki/Tower_of_Hanoi May 3, 2015 at 20:04
• Reminds me of game Solitaire. Could you use algorithm from there by any chance? Jul 2, 2015 at 22:45
• Solitaire, that is an interesting way of looking at this. I kinda put this on the back burner, but I'll give that some thought when I get back to it. Jul 7, 2015 at 6:30