How to efficiently find 10 greatest numbers from billions of numbers?

Question

Problem Statement: Find 10 maximum numbers from a file which contains billions of numbers

Input: 97911 98855 12345 78982 ..... .....

I actually came up with the below solution which has

• best case complexity O(n) - When file has numbers in descending order
• worst case complexity O(n*10) ~ O(n) When the file has numbers in ascending order
• Average complexity ~ O(n)

Space complexity is O(1) in all cases

I am reading the file using a file reader and an sorted Array which stores the maximum 10 numbers. I will check if the currentLine is greater than the smallest element in the array - If so will insert it in the correct position by swapping.

Scanner sc = new Scanner(new FileReader(new File("demo.txt")));
int[] maxNum = new int[10];
    while(sc.hasNext()){
    int phoneNumber = Integer.parseInt(sc.nextLine());
    if(phoneNumber>maxNum[9]){
        maxNum[9] = phoneNumber;
        for(int i =9;i>0;i--){
            if(maxNum[i]>maxNum[i-1]){
                int temp = maxNum[i];
                maxNum[i] = maxNum[i-1];
                maxNum[i-1] = temp;
            }
        }
    }
    }

I am looking for feedback if there are better ways to implement this

Answer 1

If the file is not sorted, you have to look at least once at every number in the file because it could be among the 10 largest. Therefore O(n) is the best you can achieve.

Some optimization is possible (however without changing the asymptotic complexity) by replacing the maxNum array with a min-heap. This will run faster if the count of numbers to be found is large enough (say you are looking for the 100 largest numbers). It will probably not yet pay off at 10.