title: Which Data structure to use to sort millions of records and what algorithm to use
body: <p>I have a situation where I have to store millions of records. At the same time, I also need to sort these records. I have following questions in my mind.</p>
  
  <ol>
  <li>Which data structure to use to save such huge amount of records?</li>
  <li>Which sorting algorithm should I use to sort the records on the above selected data structure?</li>
  <li>Should I sort the data while adding or keep adding and sort it when required?</li>
  <li>Millions of records are both ff type primitives and Objects. So I need to sort two types of records which are stored in two different data structures.</li>
  </ol>
  
  <p>When someone ask me nth smallest/nth highest data in the million records, I need to return the data back from my sorted data. I need to store this data in memory.</p>
  
  <p>I did try to find the answer but couldn't find anything concrete. Any help appreciated?</p>