Recentemente, participei de uma entrevista na qual me pediram "escreva um programa para encontrar os 100 maiores números de uma matriz de 1 bilhão de números".

Eu só consegui fornecer uma solução de força bruta que classificasse a matriz na complexidade de tempo O (nlogn) e levasse os últimos 100 números.

Arrays.sort(array);

O entrevistador estava procurando uma complexidade de tempo melhor. Tentei outras soluções, mas não consegui responder. Existe uma solução melhor para a complexidade do tempo?