The sorting doesn’t happen in constant time. The actual sort happens by hand as you take out the largest pieces first. Until you do that, they aren’t in linear order.
They're not in order, they're just in a data structure where the largest remaining element can be extracted in O(1) time. One can't say anything useful about any other elements of the list.
It's fun to think about: you have a structure which allows you to iterate all elements in order in O(n) time. Isn't this in many ways equivalent to the structure being "sorted", even if it doesn't have all the properties of a sorted array (like being able to get the nth element in O(1))?
For example, a sorted linked list behaves almost exactly like this spaghetti column.
Interesting remark. So, a "data structure where the largest remaining element can be extracted in O(1) time" can be turned into a sorted list in O(n) time.
So, under the assumtions, the overall algorithm does complete in constant time.
We know. No one is proposing this be used to actually sort. It's funny because it is a linear time algorithm, but incredibly inefficient and impractical in real life.
i've actually implemented a similar spatial-sort method used within an analog computer for some industrial controllers. so it does have some real life applications.
The traditional mechanical systems in automatic vending machines that tell and sort correct coins from wrong or fake ones are probably of the same class of mechanical "sorting" (rather categorization in this case) systems. "Mechanical coin acceptor" appears to be the established expression for it.
