Sorting technique - most efficient

An answer to this question on Stack Overflow.

Question

What sorting technique would you use to sort 10,000 items using just 1000 available slots in your RAM?

  1. Heap Sort
  2. Quick Sort
  3. Bubble Sort
  4. Merge Sort

I am confused between quick and merge sort. Both have average time complexity of nlogn but again heap sort also has the same complexity. Any inputs would be appreciated!

Answer

This seems like an HW question, so I'd prefer not to answer directly. In general, though, since your RAM is small and your list is big, you'll do best with something like a cache oblivious algorithm.