Per partition local ordering

You are right, examples (1) and (3) do not require reading all results into memory, as the end results are partially sorted only.
I think this PER PARTITION ORDER would be possible to implement.