I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?