We have been asking this question for over a decade, and so far only one applicant of hundreds has ever produced the correct algorithm.
Conclusion: either nobody reads Knuth in the CmpSci/CmpEng courses anymore, nobody teaches it, programmers have awful memories, or most coders are not very good.
Not everyone needs to solve problems like this, but if you do, recursion is one of the fastest ways to do it. At least that's how I'd tackle it.
How big a list? I think I’d probably just go with a merge sort but as I’m a tester these days and haven’t written code in a good 6 years I’m probably forgetting something.
I’ve used heapsort in the past. It is not as fast as quicksort, but it was easier to program quickly for me.
These days, I’d use the C++ STL list, and used the built-in sort() function...
Ah, I’ve re-read you first e-mail. I was thinking a generic algorithm.
If you are limited to the first 1 million numbers, you create an array of 1 million integers initialized to 0, and as you loop through the list, you increment the array at the location for that integer.
i.e, if the number is 1, you increment array item 1 (Fortran) or 0 (C/C++).
Once you have gone through the list, you loop through the array to determine the first in the list.
Correct?