| It is easy to prove that N sidings can sort at least 2**N cars. Let f(N)
be the number of cars that N sidings can sort. Then:
f(1) >= 2 (use the siding to switch cars if necessary)
f(N+1) >= 2 * f(N) (switch the f(N) cars with the largest numbers
into the first siding; the other f(N) are not switched and get sorted
by the other N sidings. When this operation completes, "pop" the
f(N) stored cars from the first siding and sort them using the other
N sidings.)
This is just a lower bound, however; while f(1) = 2 (the sequence [1 3 2]
can't be sorted into [3 2 1] with just one siding) it appears that f(2) > 4
(based on some cases I worked by hand on an airplane.....)
|
| For an upper bound to the number of cars that can be sorted by N sidings,
consider a siding (plus a little track to either side) to be a "permuting
machine" which permutes an input string into an output string. It turns
out that a single one of these "permuting machines" is capable of producing
(2**N - N) permutations of an input string of N cars. (I don't have a proof
of this, just an enumeration for small N; the proof looks like it will
consist of quoting the right magic line in "Summation of Series", tho)
When these permuting machines are cascaded, with one machine's output
serving as the next one's input, the total number of producable permutations
is limited by the product of the number of permutations produced by each
machine; since all machines are identical, this means that K sidings can
produce no more than (2**N - N) ** K permutations of an N-car train.
Well, if this is less than the total number of permutations of such a train
(which is N factorial) then there is an unreachable permutation and thus
an unsortable sequence of cars. Thus the number of cars that can be sorted
by K sidings is limited by the inequality:
(2**N - N) ** K >= N! ;achievable perms >= possible perms
This is stronger than the inequality:
2 ** (N*K) > N!
Which is stronger than the inequality:
(2**K) ** N > (N/e) ** N ; N! ~= (N/e)**N * SQRT(2*PI*N) * ...
Taking Nth roots:
2**K > N/e
or N < e * 2**K
Given the previous note (in which, by the way, the algorithm given is
really a Quicksort with optimal partitions) we have 2**N =< f(N) < e*2**N
|