Suppose one has a physical pile of cards. Each card is labelled with a number, which were annotated. As an actual example, I have a pile of 560 cards in that exact order:
[36, 32, 30, 21, 73, 90, 9, 24, 81, 27, 65, 15, 53, 82, 28, 43, 45, 21, 41, 69, 38, 39, 6, 17, 67, 20, 54, 37, 65, 18, 38, 14, 68, 73, 30, 4, 13, 39, 3, 14, 36, 68, 18, 4, 82, 43, 1, 18, 41, 71, 24, 70, 1, 4, 23, 39, 20, 28, 30, 37, 39, 41, 49, 79, 43, 22, 55, 70, 3, 22, 28, 82, 3, 12, 70, 24, 54, 78, 19, 49, 41, 27, 41, 67, 10, 23, 24, 20, 27, 44, 80, 70, 41, 6, 21, 20, 48, 73, 54, 1, 7, 67, 38, 26, 66, 30, 43, 36, 55, 16, 24, 27, 28, 43, 28, 1, 3, 9, 38, 19, 88, 65, 68, 21, 44, 36, 6, 39, 67, 6, 69, 49, 56, 39, 49, 41, 50, 18, 82, 17, 22, 47, 68, 18, 24, 53, 51, 68, 53, 65, 1, 7, 7, 38, 55, 55, 16, 67, 82, 78, 70, 1, 20, 30, 54, 73, 78, 82, 20, 20, 22, 27, 30, 32, 65, 78, 44, 9, 12, 31, 3, 70, 24, 4, 54, 3, 28, 39, 49, 55, 66, 69, 70, 9, 21, 24, 54, 71, 13, 6, 67, 38, 22, 50, 36, 30, 1, 12, 9, 24, 44, 48, 54, 78, 3, 21, 32, 56, 66, 68, 70, 82, 80, 10, 28, 28, 29, 41, 43, 43, 45, 43, 74, 55, 2, 50, 74, 38, 67, 27, 51, 67, 38, 36, 11, 70, 41, 6, 65, 39, 49, 4, 17, 41, 27, 6, 10, 56, 82, 55, 66, 73, 78, 73, 55, 70, 3, 68, 67, 20, 54, 15, 25, 43, 49, 54, 68, 79, 69, 24, 55, 78, 37, 74, 73, 3, 67, 30, 65, 18, 53, 31, 38, 39, 38, 2, 16, 39, 6, 67, 80, 20, 66, 14, 27, 9, 36, 47, 21, 41, 1, 24, 54, 56, 11, 70, 1, 19, 4, 17, 30, 36, 38, 38, 44, 67, 36, 19, 65, 27, 30, 15, 36, 21, 41, 69, 9, 38, 65, 68, 21, 36, 14, 17, 68, 18, 24, 44, 74, 73, 54, 1, 1, 31, 49, 24, 55, 78, 73, 3, 10, 68, 73, 30, 7, 23, 82, 43, 2, 70, 27, 54, 80, 68, 73, 30, 47, 79, 51, 38, 39, 6, 67, 20, 54, 67, 6, 39, 13, 49, 41, 27, 56, 66, 18, 24, 6, 9, 67, 65, 27, 82, 20, 78, 25, 23, 50, 81, 20, 27, 70, 47, 41, 6, 24, 28, 43, 28, 51, 70, 1, 39, 78, 68, 10, 74, 21, 20, 3, 73, 54, 30, 2, 78, 9, 73, 37, 47, 21, 30, 65, 79, 23, 18, 37, 20, 53, 41, 67, 6, 4, 18, 39, 49, 41, 57, 28, 8, 55, 48, 1, 39, 20, 7, 27, 70, 41, 30, 20, 41, 16, 67, 6, 39, 25, 8, 49, 18, 82, 19, 55, 12, 70, 8, 55, 44, 3, 65, 11, 2, 3, 54, 9, 78, 22, 71, 50, 39, 49, 18, 22, 13, 82, 55, 36, 29, 15, 27, 28, 28, 49, 39, 9, 18, 9, 78, 68, 44, 21, 20, 3, 50, 29, 7, 82, 20, 78, 66, 32, 30, 43, 82, 43, 1, 23, 49, 24, 55, 37, 9, 22, 38, 65, 68, 20, 21, 36, 12, 18, 41, 43, 14, 28, 82, 3, 6, 25, 81, 21, 41]
My question is: given such list, what is the best algorithm for an human to execute that will sort the list least possible amount of quick human moves? By quick human move, one can visualize the cards are stacked in a table, so a person can either move 1 card from a pile to another (up to a small finite limit of possible simultaneous piles), or place an entire pile on top of another (as this obviously should count as a single movement).
Assumptions
The person sorting the cards has the following information:
91 stacks: one stack per value
The best case scenario is obviously the one where there is enough space on the table for the unsorted stack plus as many stacks as there are different values. In this case, every card is put on a stack according to value, after which stack 89 is put on top of stack 90, stack 88 is put on top of stacks 89, and so on until there is one ordered stack. The number of required actions equals the number of cards plus the number of seperate values (560 + 64 in the example).
The person doesn't know whether there will be any values missing from the range, so he can only use this strategy if there is space for 91 stacks.
33 stacks or less: ordered sub-stacks
If there isn't enough space for 91 stack, the following strategy could be used:
Take every following card, and either:
For the example array, this algorithm can be done in one go if there is space for 33 stacks (1 input stack, 1 ordered stack, 1 empty place to merge stacks, 30 ordered sub-stacks). This would take 560 + 560 actions; it's obviously less efficient because all the cards have to be moved one by one at least twice.
The number of rounds depends on whether you start by sorting up or down; for the example array, down seems to be the best choice. With unknown input, the best choice cannot be known in advance; the difference is never more than 1 round, though.
Numbered stacks
The method mentioned above with 91 stacks can be adapted for fewer stacks. You use the available space for sub-stacks for the N highest values, and put the lower values on an unordered stack. When all cards have been moved, you stack the numbered sub-stacks, and start again with the unordered stack as the input stack. Every round you look for N lower values, until you've done the whole range. The advantage over the previous method is that the sub-stacks are moved per stack, and not per individual card. The results are better, except for the range 33 to 39.
This is the number of rounds and actions per total number of stacks:
| ORDERED SUB-STACKS (UP FIRST / DOWN FIRST) | NUMBERED STACKS
stacks | rounds actions per card | rounds actions per card
91 1 1 1120 1120 2.0 2.0 1 624 1.1
...
48 1 1 1120 1120 2.0 2.0 2 973 1.7
...
40 1 1 1120 1120 2.0 2.0 3 1111 2.0
39 1 1 1120 1120 2.0 2.0 3 1125 2.0
38 1 1 1120 1120 2.0 2.0 3 1159 2.1
37 1 1 1120 1120 2.0 2.0 3 1207 2.2
36 1 1 1120 1120 2.0 2.0 3 1226 2.2
35 2 1 1674 1120 3.0 2.0 3 1247 2.2
34 2 1 1635 1120 2.9 2.0 3 1263 2.3
33 2 1 1559 1120 2.8 2.0 3 1280 2.3
32 2 2 1521 1644 2.7 2.9 4 1318 2.4
31 2 2 1512 1627 2.7 2.9 4 1344 2.4
30 2 2 1504 1607 2.7 2.9 4 1368 2.4
29 2 2 1458 1518 2.6 2.7 4 1408 2.5
28 3 2 1945 1499 3.5 2.7 4 1455 2.6
27 3 2 1923 1473 3.4 2.6 4 1501 2.7
26 3 3 1905 1999 3.4 3.6 4 1560 2.8
25 3 3 1883 1979 3.4 3.5 5 1629 2.9
24 3 3 1822 1899 3.3 3.4 5 1697 3.0
23 4 3 2255 1802 4.0 3.2 5 1788 3.2
22 4 4 2206 2286 3.9 4.1 5 1854 3.3
21 4 4 2070 2197 3.7 3.9 5 1880 3.4
20 5 5 2441 2512 4.4 4.5 6 2037 3.6
19 6 5 2876 2410 5.1 4.3 6 2165 3.9
18 6 5 2659 2313 4.7 4.1 6 2247 4.0
17 7 7 3021 2804 5.4 5.0 7 2350 4.2
16 7 8 2926 3071 5.2 5.5 7 2500 4.5
15 8 9 3302 3546 5.9 6.3 8 2680 4.8
14 12 11 4686 4363 8.4 7.8 9 2930 5.2
13 14 13 5241 4729 9.4 8.4 9 3187 5.7
12 16 17 5481 5826 9.8 10.4 10 3458 6.2
11 19 18 6262 5985 11.2 10.7 12 3900 7.0
10 24 23 7679 7421 13.7 13.3 13 4385 7.8
9 32 33 10477 10719 18.7 19.1 15 5038 9.0
8 41 40 12187 12130 21.8 21.7 18 6030 10.8
7 54 55 16464 16488 29.4 29.4 23 7427 13.3
6 82 83 25293 25326 45.2 45.2 30 9784 17.5
5 150 151 42225 42230 75.4 75.4 45 14529 25.9
4 334 335 93301 93305 166.6 166.6 89 28717 51.3
3 - - - - - - - - -
UPDATE:
Sub-ranges of varying size
A better version of the numbered stacks method would be to split the unordered stack into sub-ranges, and subsequently split each sub-range into numbered stacks and add them to the ordered stack. With each sub-range that is processed, an additional stack space is freed, so the ranges can become increasingly large.
In the example, the highest cards are put on seperate stacks, lower cards are lumped together in ranges, down to the lowest cards which are part of an eleven-value range (1-11). The required number of stacks to run this algorithm in one go is the number of values in the biggest range plus one, thus 12 in the example.
Taking into account the original version of your question, which asked for an efficient sorting method for a list with a known initial order, I have used knowledge of the cards in the stack to make a few additional optimizations to the example:
Using this method, and knowledge of the initial order, the number of required actions for a table with 12 stacks is 1158 actions, which is much lower than the 5826 actions (or 33 stacks) and 3458 actions (or 38 stacks) required by the ordered sub-stacks or numbered stacks methods.
The following diagram shows the value or range of values of the cards in each of the 12 stacks. Every line shows a step in the algorithm, and in the column on the right you'll find the number of actions required to reach this step.
1 2 3 4 5 6 7 8 9 10 11 12
ACTIONS
1-65
65 64 63 62-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 560
65-63 62-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 2
65-62 61 60 59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 25
65-59 58-54 53-47 46-40 39-32 31-22 21-12 11-1 3
65-58 57 56 55 54 53-47 46-40 39-32 31-22 21-12 11-1 42
65-54 53-47 46-40 39-32 31-22 21-12 11-1 4
65-53 52 51 50 49-48 47 46-40 39-32 31-22 21-12 11-1 73
65-47 46-40 39-32 31-22 21-12 11-1 5
65-46 45 44 43 42 41 40 39-32 31-22 21-12 11-1 52
65-40 39-32 31-22 21-12 11-1 6
65-39 38 37 36 35 34 33 32 31-22 21-12 11-1 96
65-32 31-22 21-12 11-1 7
65-31 30 29 28 27 26 24+25 23 22 21-12 11-1 82
65-22 21-12 11-1 8+1
65-21 20 19 18 17 16 15 14 13 12 11-1 82
65-12 11-1 9
65-11 10 9 8 7 6 5 4 3 2 1 91
65- 1 10
----
1158
In general, with unknown initial sorting, 12 stacks will sort N cards with a maximum of 66 distinct values (11 + 10 + 9 + ... + 1), and the number of actions is N + (N - #66) + 10 + 9 + 8 + ... + 1 where #66 is the number of cards with the highest value (because these don't have to be moved twice).
1 2 3 4 5 6 7 8 9 10 11 12 <-STACKS
ACTIONS
1-66
66 65-64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 N
66-65 64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #65-64
66-64 63-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 1
66-63 62 61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #63-61
66-61 60-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 2
66-60 59 58 57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 #60-57
66-57 56-52 51-46 45-39 38-31 30-22 21-12 11-1 3
66-56 55 54 53 52 51-46 45-39 38-31 30-22 21-12 11-1 #56-52
66-52 51-46 45-39 38-31 30-22 21-12 11-1 4
66-51 50 49 48 47 46 45-39 38-31 30-22 21-12 11-1 #51-46
66-46 45-39 38-31 30-22 21-12 11-1 5
66-45 44 43 42 41 40 39 38-31 30-22 21-12 11-1 #45-39
66-39 38-31 30-22 21-12 11-1 6
66-38 37 36 35 34 33 32 31 30-22 21-12 11-1 #38-31
66-31 30-22 21-12 11-1 7
66-30 29 28 27 26 25 24 23 22 21-12 11-1 #30-22
66-22 21-12 11-1 8
66-21 20 19 18 17 16 15 14 13 12 11-1 #21-12
66-12 11-1 9
66-11 10 9 8 7 6 5 4 3 2 1 #11- 1
66- 1 10