Parcurgi lista de fisiere (acel while al tau), extragi data din fiecare nume (explode dupa _), o convertesti in timestamp (strtotime) si formezi un array cu fisierele.
Ex.: $FILES_LIST[$file_timestamp] = $file;
Apoi sortezi $FILES_LIST, apoi parcurgi array-ul si-l afisezi. In loc de $file, cand formezi array-ul de fisiere, poti sa-l faci un pic mai "complex", adica de forma:
<?php
$FILES_LIST[$file_timestamp] = array(
"name"=>$file_name, // aici trebuie sa extragi numele din path banuiesc
"path"=>$file,
"size"=>$file_size, // aici iei filesize-ul dupa $file
// etc
);
?>