CareerCup

It's an array so I'd do a radix sort. 32 passes and done.

What does " stored in an array" mean? If you are to write a function that takes an array as input then use quicksort - caller has figured out how to get the data in memory already :)

If you are two read the data from disk - then external merge sort is the way to go.

External Merge Sort!!!

for the huge amount of data the quick short is the best when data are in worst case. other wise aply merg short.

some one explain me about external sort plzzz??

If you assume that the entire array fits in memory, I would choose heap sort since it can be done in place (O(1) additional space) and is guaranteed O(n lgn) time, where as quicksort requires worst case O(n) additional space (maybe the array fits in memory but not the additional space required for quicksort) and takes O(n^2) in the worst case.

Otherwise, if you don't assume the array can entirely fit in memory, external merge sort is a good option.

radix sort ..min time

why not just using counting sort. allocate 1 billion continuous memory of int with zero. considering each integer as the memory address, increment the corresponding memory address by one for each integer. Print out the memory address by number of times in each address. complexity O(2*n)

Because it's a billion integers.
If we go by understanding integer data type, we can create an array of size equal to integer data space which is 4GB.
And take a single pass through billion integers to find the count of each and remember them in 4gb array.
Next pass go through 4b array and write the non-zero count numbers back into first array.