Ordini con il quicksort (O(n log n)), quindi per individuare gli elementi duplicati ti basta scorrere l'array una sola volta, visto che nell'array ordinato tutti i duplicati dello stesso elemento sono consecutivi.
quindi in luogo di due cicli nidificati ne hai uno solo che confronta l'elemento n e n+1 giusto?