"Consider a set X of n positive integers to be sorted and assume the biggest number in X is m. Then, the frame should have at least m rods and n levels." (see linked article below for illustration)
Algorithm as expressed in the article: For all x ∈ X, drop x beads (one bead per rod) along the rods, starting from rod 1 to rod x. Finally, the beads, seen level by level, from level n to the first level, represent X in ascending order.
"The Algorithm Bead-Sort is correct. We prove the result by mathematical induction on the number of rows of beads. We claim (1) that the set of positive integers represented by the states of the frame before and after the beads are dropped is the same. Also we claim (2) that the number of beads on each row i, after dropping, is at most the number of beads on row i - 1 (the row directly below it).
Consider a set of cardinality n = 1. Since there is no possibility for a bead to drop the above two claims hold. Now assume these two properties hold for an input set whose cardinality is k. Suppose a row k + 1 of m'< m beads is now dropped on top of these k rows. Since claim (2) holds there is an index j ≤ m' such that all m' - j beads in columns greater than j drop down (from row k + 1). If m' - j = 0, we are done. Otherwise, the values of row k + 1 and row k have been swapped, with any excess beads on row k ready to drop further. Thus, claim (1) holds, after a series of at most k swaps. Claim (2) also holds since we repeat these swaps until the force of gravity cannot pull down any more beads."
I'm having trouble understanding the relevance of some of the assumptions in this proof:
Why does it matter if row k + 1 has m' < m beads? It seems to me the proof works even if m' > m or m' = m.
"There is an index j ≤ m' such that all m' - j beads in column greater than j drop down (from row k + 1)." How does this follow from claim (2)?
It isn't clear to me why claim (2) holds at the end of the proof. What is the author trying to convey here?
Here's a link to the article containing the algorithm and proof: https://researchspace.auckland.ac.nz/bitstream/handle/2292/3679/171joshua.pdf
Here's a Wiki link: https://en.wikipedia.org/wiki/Bead_sort