title: Sorting millions of int/string pairs using Java
body: <p>I have 50,000,000 (integer, string) pairs in a text file. The integers are times in milliseconds, so are 13 digits long (e.g. 1337698339089).</p>
  
  <p>The entries in the text file are like this:</p>
  
  <pre><code>1337698339089|blaasdasd
  1337698339089|asdasdas
  1337698338089|kasda
  </code></pre>
  
  <p>There can be identical entries.</p>
  
  <p>I want to sort the entries on the integers (in ascending order) preserving any duplicate integers and preserving the (integer, string) pairs. The approach I have taken is leading to  memory errors, and so I'm looking for alternative approaches.</p>
  
  <p>My approach is something like this (using some pseudo-code):</p>
  
  <pre><code>// declare TreeMap to do the sorting
  TreeMap&lt;Double, String&gt; sorted = new TreeMap&lt;Double, String&gt;();
  
  // loop through entries in text file, and put each in the treemap:
  for each entry (integer, string) in the text file:
  
     Random rand = new Random();
     double inc = 0.0;
  
     while (sorted.get(integer + inc) != null) {
         inc = rand.nextDouble();
     }
  
     sorted.put(integer + inc, string);
  </code></pre>
  
  <p>I am using random numbers here to ensure that duplicate integers can be entered in the treemap (by incrementing them by a double between 0 and 1).</p>
  
  <pre><code>// to print the sorted entries:
  for (Double d : sorted.KeySet()) {
      System.out.println(Math.round(d) + "|" + sorted.get(d));
  }
  </code></pre>
  
  <p>This approach works but breaks down for 50,000,000 entries (I think because the treemap is becoming too large; or possibly because the while loop is running for too long).</p>
  
  <p>I would like to know what approach more experienced programmers would take.</p>
  
  <p>Many thanks!</p>