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)?

  • 2
    $\begingroup$ Like he said, don't use bubble sort. $\endgroup$ – saadtaame Jun 28 '14 at 0:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.