Give efficient algorithms for finding the largest k values (in order) out of

Give efficient algorithms for finding the largest k values (in order) out of
a set of n, using comparisons only (e.g. no hashing), in the case where:
(a) k = 3 (b) k = n/2; (c) k = log(n).
(You can use a different algorithm for each case.)
State the asymptotic worst-case running time of your algorithms.
For (a), we use tournament algorithm, which has done this by n-1+logn-1+logn-2+logn-1, O(n+klogn-m) comparison
For (b), we use selection algorithm, which has done this by O(n) if the pivot is the median of the median of the array
For (c), we use minheap, which has done this by O(nlogk), notice when we heapify the min heap, do comparison on two child nodes first, and then swap the parent node with the smaller one, that is where the logk come from

Find the kth min/max out of n numbers,

Find the kth min/max out of n numbers,

1) max heap, heap size k, O(nlogk)
2) 2^32 bit vector, use the value of integer as index to set bit vector, then the indexes of max k set bits are max k integers, O(n)
3) selection algorithm to find kth number then scan the array again to find the value smaller than this number O(n)

Given a big set which contains 1 billion random numbers(not sorted and

Given a big set which contains 1 billion random numbers(not sorted and
there maybe some duplicates),how to find 1 million largest numbers in it
(a)using just one single machine.(You need to consider the memory constraint)
(b)using multiple machines. How to design it? Need to give the details.

(a) External selection algorithm
(b) distributed selection algorithm