Ci sono due questioni. Innanzitutto quella fondamentale. Se durante un sort vuoi far mostrare/aggiornare qualcosa, allora il sort deve essere eseguito in un thread che non sia il Event Dispatch Thread. Con tutto quello che ovviamente comporta in termini di multi-threading, sincronizzazione, ecc...
In una applicazione Swing, se fai un sort (o qualunque altra operazione "lunga") nel contesto del EDT (es. a seguito di un evento), stai tenendo tu impegnato il EDT e quindi nulla può essere aggiornato visivamente.
La seconda questione è che se usi Collections.sort() sai solo quando inizia e quando finisce (cioè fai tu qualcosa appena prima e appena dopo). Non hai nessun'altra informazione. Non c'è alcuna API o callback che permetta di sapere cosa sta facendo, a che punto è, quanto tempo anche stimato gli rimane, ecc... Insomma, non c'è alcun appiglio su questi aspetti.
Se implementassi tu un algoritmo di ordinamento, chiaramente uno di quelli noti (difficilmente se ne "inventano" di nuovi), e magari lo rendi generalizzato in funzione di Comparable/Comparator, allora avresti più controllo. Potresti offrire una API apposita per fornire informazioni sull'avanzamento e cose del genere.