Credo che la soluzione migliore e usare l'order by.
Ti costa qualcosa in termini di calcolo ed esecuzione della query ma sicuramente ti costa meno rispetto ad un possibile ordinamento fatto in php.
Credo che se stabilisci che il campo su cui fai l'ordinamento è un indice riduci il tempo di calcolo.
E' da verificare, ciao