What is the most efficient way to sort 1 million 32-bit integers? Tips: Explain

Question

What is the most efficient way to sort 1 million 32-bit integers?
Tips: Explain your response considering both time and space complexity, and make sure to discuss best, average and worst case scenarios.

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

the most efficient way of sorting would have been Bucket sort with respect to time, using bucket sort, space required would shoot up beyond 30GB!!! So we cannot perform bucket sort on this data.

The next most efficent way of sorting would be Merge sort or Quick sort, but in case of Quick sort, the worst case complexity is in the order of n2. In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. So let us opt for merge sort.

One drawback of merge sort, when implemented on arrays, is its O(n) working memory requirement. So we shall not have all the numbers loaded into the memory. But I am working in an optimizing the performance of merge sort and there exists Cache-aware versions of the merge sort algorithm, that focuses specifically to minimize the movement of pages in and out of a machine's memory cache, have been proposed. For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size X are reached, where X is the number of data items fitting into a CPU's cache and registers. Each of these subarrays is sorted with an in-place sorting algorithm such as insertion sort, to reduce swaps, and normal merge sort is then completed in the standard recursive fashion.

Even the biggest advantage of merge sort in our case can be achived with the use of linked list. With the use of Linked-List. It is easy to implement a merge sort in such a way that it requires only (1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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