title: Fastest way to find duplicate lines in 50GB+ text file
body: <p>I'm trying to check to make sure an encryption algorithm I wrote is one-to-one. To do so, I looped through the program and wrote all of the outputs (2^32 of them) to a file, one per line. The file is sitting at just over 50GB, after about 9 hours of runtime.</p>
  
  <p>Now I need to run through all of the output lines to verify that there are no duplicates. Here is some sample output:</p>
  
  <pre><code>PAAA#0+//V8//
  PAAA#o+//37//
  PAAA#Q+//Z7//
  ZAAA#d///#
  ZAAA#J///#
  ZAAA#/+//#
  </code></pre>
  
  <p>The easiest way I know would be to compare each line with all of the lines following it, but that would be theta(n!) and I don't really think I can stand to wait that long, considering n is 2^32. </p>
  
  <p>Is there a way I can do this kind of comparison in O(n) or O(n log n) time? I'm not opposed to re-outputting it to a database if that would go faster - I was just trying to save disk space at this point. </p>
  
  <p>I wrote the program in c++ on Win7, but I'm not opposed to using other languages on other OSes if it can be done much faster. </p>
  
  <p>Thanks in advance for the help, guys!</p>