title: Linux: sorting a 500GB text file with 10^10 records
body: <p>I have a 500GB text file with about 10 billions rows that needs to be sorted in alphabetical order. What is the best algorithm to use? Can my implementation &amp; set-up be improved ?</p>
  
  <p>For now, I am using the coreutils sort command:</p>
  
  <pre><code>LANG=C
  sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile
  </code></pre>
  
  <p>I am running this in AWS EC2 on a 120GB RAM &amp; 16 cores virtual machine. It takes the most part of the day.</p>
  
  <p>/volatile is a 10TB RAID0 array. </p>
  
  <p>The 'LANG=C' trick delivers a x2 speed gain (thanks to <a href="https://stackoverflow.com/questions/1935155/sorting-a-text-file-with-over-100-000-000-records">1</a>)</p>
  
  <p>By default 'sort' uses 50% of the available RAM. Going up to 80-90% gives some improvement.</p>
  
  <p>My understanding is that gnu 'sort' is a variant of the merge-sort algorithm with O(n log n), which is the fastest : see <a href="https://superuser.com/questions/234054/unix-sort-algorithm-implementation">2</a> &amp; <a href="http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms" rel="nofollow noreferrer">3</a> . Would moving to QuickSort help (I'm happy with an unstable sort)?</p>
  
  <p>One thing I have noticed is that only 8 cores are used. This is related to default_max_threads set to 8 in linux coreutils sort.c (See <a href="http://lingrok.org/xref/coreutils/src/sort.c" rel="nofollow noreferrer">4</a>). Would it help to recompile sort.c with 16 ?</p>
  
  <p>Thanks!</p>
  
  <hr>
  
  <p>FOLLOW-UP :</p>
  
  <p>@dariusz</p>
  
  <p>I used Chris and your suggestions below. </p>
  
  <p>As the data was already generated in batches: I sorted each bucket separately (on several separate machines) and then used the 'sort --merge' function. Works like a charm and is much faster: O(log N/K) vs O(log N). </p>
  
  <p>I also rethinked the project from scratch: some data post-processing is now performed while the data is generated, so that some un-needed data (noise) can be discarded before sorting takes place.</p>
  
  <p>All together, data size reduction &amp; sort/merge led to massive reduction in computing resources needed to achieve my objective.</p>
  
  <p>Thanks for all your helpful comments.</p>