"This is why you won't get asked to sort 1 million integers in 1MB of memory" is of course a double trick question.

If you get stuck on it then you've probably failed to see that 1 million ints won't fit in a meg. But if you dismiss it by saying "1 million ints won't fit in a meg" you've failed to see that it's a platform dependent question, and on some platforms 1 million ints can fit in a meg. If you further realize that megabyte is a term that is tossed around fairly loosely you can argue for another ~48000 bytes to use for local variables, and then standard sorting algorithms can work.

You can even take it further, because you have a bound on the problem size you can show that in this situation naive bubblesort runs in constant time.

Edit: May I ask a clarifying question? Is the list already sorted?

If you get stuck on it then you've probably failed to see that 1 million ints won't fit in a meg. But if you dismiss it by saying "1 million ints won't fit in a meg" you've failed to see that it's a platform dependent question, and on some platforms 1 million ints can fit in a meg. If you further realize that megabyte is a term that is tossed around fairly loosely you can argue for another ~48000 bytes to use for local variables, and then standard sorting algorithms can work.

You can even take it further, because you have a bound on the problem size you can show that in this situation naive bubblesort runs in constant time.

Edit: May I ask a clarifying question? Is the list already sorted?