Describe an efficient algorithm to sort 10 billion 32-bit integers in a computer

Question

Describe an efficient algorithm to sort 10 billion 32-bit integers in a computer with 8Gb RAM? Tips: Again, explain your response considering both time and space complexity, making sure to discuss best, average and worst case scenarios. Also notice the following:

1 gigabyte = 8,589,934,592 bits 1 integer = 32 bits Therefore, only 8x(8,589,934,592/32) = 8x(268,435,456) ~= 2 billion integers can be stored in memory at a time. * The actual number is smaller because of other software already running on the computer.

Explanation / Answer

Since we are not aware of the range of data being stored, so we cannot use Bucket short

Sicne the memory cannot hold the complete data at once, its better we dont use Merge Sort

Selection sort and bubble sort are of order O(n2) and thus not at all efficient.

So the best way would be:
       divide the data into 5 subsets of size 2 billion each and apply quick sort on each subsets (this is done so that all the numbers being sorted are present in the main memory and sorted much efficiently and our chocie is quick sort since it among the fastest sorting algo with Size complexity O(1))
Once we are done with this, the set is partially ordered and its better we perform merging now. Merge sort is a stable sort and is more efficient at handling slow-to-access sequential media ie secondary memory where the data is stored.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.