Obama on sorting 1M integers: Bubble sort the wrong way to go

Recently StackOverflow and Hacker News discussed the question of how to sort 1 million 8-digit numbers in 1 megabyte of RAM. This reminded me of when I saw Obama in 2007 at Google - Eric Schmidt asked Obama how to sort 1 million integers as a laugh line, but Obama shocked him by answering "I think the bubble sort would be the wrong way to go." The video is pretty entertaining:

Here's the transcript:

SCHMIDT: Now, Senator, you're here at Google and I like to think of the presidency as a job interview. Now, it's hard to get a job as president. And--I mean, you're going to do a great job. It's also hard to get a job at Google. We have questions and we ask our candidates questions. And this one is from Larry Schwimmer. What--you guys think I'm kidding, it's right here.[1] What is the most efficient way to sort a million 32-bit integers?

OBAMA: Well...

SCHMIDT: Maybe--I'm sorry...

OBAMA: No, no, no, no. I think--I think the bubble sort would be the wrong way to go.

SCHMIDT: [facepalm] Come on. Who told him this? Okay. I didn't see computer science in your background.

OBAMA: We've got our spies in there.[2]

If you're wondering about the complete answer to the sorting question, see a detailed explanation.[3]

All in all, it was a very unexpected answer from Obama with perfect delivery.

Notes

[1] Nervous laughter greeted the mention of a Larry Schwimmer question, because he once asked Jimmy Carter about his UFO encounter.

[2] Eric Schmidt had asked the sorting question to John McCain on a different visit, with the expected result. See the YouTube clip of McCain's visit.

[3] The pedantic may note that Obama's question is slightly different from the Stack Overflow question since it involves 32-bit integers vs. 8 digit integers, and the memory constraint was omitted.