CareerCup

can you be bit more clear?

For 5 billion numbers, if we want distinct numbers in sorted order we can use sortedset interface.

If its key value pair we can use sortedmap interface

sort 1000 at a time then sort those over and over again like the mergesort

external sort, split it into many segments and sort them in many pass

For these kind of sorting best way is to have Map Reduce algorithm

use external sort. It's primary purpose is to sort large data sets that don't fit in the main memory. Following is the excellent lecture by sahi Simpson. MIT prof

video.google.com/videoplay?docid=-978892635109400080

Counting sort for sorting 5 billion numbers, we'd need an auxiliary array occupying ~20GB space. If we don't have that much memory at hand [which we might in case of production systems] then we'd have to resort to External sort.

map reduce cannot be used to sort. It can be used to sort if you are planning to use counting..however if there are a billion distinct numbers then this approach wont work as well..