3 4 2 1-4
2 3 1 0-3
1 2 0 0-2
0 1 0 0-1
In this algorithm, the last column is reserved for the number of numbers in the sequence.
In this algorithm,first we write the sequence and then put the number of numbers in the last column.(This is the second step)
Then we subtract it by 1 and repeat the second step. Repeat until, there is only 1 in the digits.However,the numbers which are zero cannot be subtracted.
The last column counts the number of digits in the sequence and gathering the numbers from bottom to top gives us the ascending order sequence.
I was able to prove it for consecutive distinct integers.
But, i can't seem to prove it for random sequences such as (5, 2 ,1, 1, 1) although it does work and it takes in total two tries.
PLease help me prove this.
If any queries please comment.
I got this sorting algorithm from here-
I suspect the entire question here is to explain in layman terms how the algorithm from the linked question works. I will draw some patterns of squares below, which are, essentially, Ferrer's diagrams.
Suppose we want to sort the sequence $1,4,2$. Represent the numbers as columns of, say, squares:
$$\begin{array}{ccc} \blacksquare&\blacksquare&\blacksquare\\ &\blacksquare&\blacksquare\\ &\blacksquare\\ &\blacksquare \end{array}$$
The first pass of the algorithm produces the numbers $3,2,1,1$, which is what you get when you make all the squares "slide" to the left:
$$\begin{array}{ccc} \blacksquare&\blacksquare&\blacksquare\\ \blacksquare&\blacksquare\\ \blacksquare\\ \blacksquare \end{array}$$
(which, incidentally, sorts the sequence!), and then "flip" this diagram by swapping rows with columns and vice versa:
$$\begin{array}{ccc} \blacksquare&\blacksquare&\blacksquare&\blacksquare\\ \blacksquare&\blacksquare\\ \blacksquare \end{array}$$
You see that the first operation (slide) already sorted your numbers but the second operation (flip) was undesirable. That is why you apply your sorting algorithm once again. Now there is nothing to "slide" (the sequence $3,2,1,1$ is already sorted), but a "flip" happens again:
$$\begin{array}{ccc} \blacksquare&\blacksquare&\blacksquare\\ \blacksquare&\blacksquare\\ \blacksquare\\ \blacksquare \end{array}$$
and we are (after two "flips") back where we were after the original " slide", i.e. with a sorted sequence $4,2,1$.
Note that the algorithm in general requires two passes. You may get away with only one pass if the picture (Ferrer's diagram) after the first "slide" happens to be symmetrical with respect to swapping rows with columns.