[Solved]: Difference in Sorting 32- and 64-bit Integers

Problem Detail: 

In 2007, Barrack Obama was interviewed at Google.

The question was, "What is the best way to sort a million 32-bit integers?" Does the fact that the size range of the integer was specified elude to a different way to sort integers of different sizes (i.e., 64- or 32-bit)?

Asked By : user103853

Answered By : D.W.

Yes. For instance, sorting a million 5-bit integers is a lot easier: use counting sort. And sorting a million long strings is a different question than sorting a million 32-bit integers.

In the case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an in-memory sorting algorithm (e.g., quicksort) rather than an external sorting algorithm. If we didn't know the size of the items we were sorting, we wouldn't know whether they would fit in memory and thus wouldn't know whether it's more appropriate to use an in-memory sorting algorithm or an external sorting algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28046

3.2K people like this

 Download Related Notes/Documents