You are looking for a selection algorithm, which selects the k
th largest element in an array. The Wikipedia article gives an O(n) algorithm to do this which is similar to quicksort, but does not sort the entire array, and thus avoids the O(n*logn) runtime.
If the elements are all bounded in a certain range (e.g. 1-1000000 in your case), then another approach is to sort them using counting sort or bucket sort in O(n), and then select the element you need. Since in this case the "vast majority" of elements is under 1000000 rather than all of them, you can perform a bucket sort with 1000001 buckets, and use the last bucket for all elements above 1000000.