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.
