camel & banana puzzle
June 12, 2012
Level-wise traversal of a binary tree
June 12, 2012

sorting 1 billion numbers

Which sorting algorithm will you use to sort 1 billion numbers.

Solution:

Generally speaking, Quick sort is probably the best algorithm to sort numbers when nothing is given about the nature (like range, order etc.) of numbers.

If the range of numbers is very small, for example, if there are 10000 numbers all in the range of 1 to 10, then we can use counting sort algorithm which is a non-comparison sorting algorithm and gives O(n) worst case time in this case.

If given numbers are almost sorted then Insertion sort is a better choice than Quick Sort.

But this is a typical case, because in this case the numbers are very large, so they cannot accomodate in RAM. It means some of the numbers will be in External memory and will be swapped from external memory to RAM (using the concept of virtual memory). In such cases the choice of algorithm will be made to reduce the number of read/write from External memory and not the number of CPU cycles only. (For example, if an algorithm is taking O(n3) time but is it making very few number of swaps between external drive and RAM then it may be better than an algorithm which takes less time but is making more swaps)

Such cases are called ‘External Sorting’, and this is a typical case of External Sorting. So we need to look for a good External Sorting algorithm.

Hence, Merge Sort is a good choice for the given case.

Leave a Reply

Your email address will not be published. Required fields are marked *