Io so eliminare i doppioni senza riordinare!!! Eehhe.

Mi creo una mappa di appoggio (HashMap) e faccio una scansione degli elementi, se un elemento è già nella mappa allora è un doppione, altrimenti lo inserisco nella mappa.

Visto che la mappa è fatta di coppie chiave-valore, la chiave può essere l'elemento, il valore invece il numero di volte in cui compare nella lista originale. Così alla fine della scansione la mappa contiene tutte le informazioni necessarie.

La scansione dei dati e della mappa si fanno ovviamente in tempo lineare, inserimento e ricerca nella mappa richiedono un tempo di ordine logaritmico.
Quindi siamo sempre su n * logn complessivo.

Però siamo fuori dal contesto dell'esercizio, pazienza...