title: Interview puzzle: Sorting a million number input with limited memory
body: <p>I tried answering this using external sort, but interviewer replied that the complexity was to high n.n(log(n)) i.e. n square *logn.
  Is there a better alternative.</p>
  
  <p>To simplify the question:
  Lets suppose we have 1000 elements to sort with space allocated for 100 elements only. What is the best algorithm that will take lesser time than the external sort.</p>