<p>We are often suggested to sort the input bed file by "sort -k1,1 -k2,2n" in order to invokes a memory-efficient algorithm designed for large files, for example, <a href='https://code.google.com/p/bedtools/'>bedtools</a> intersect ( <a href='http://bedtools.readthedocs.org/en/latest/content/tools/intersect.html'>http://bedtools.readthedocs.org/en/latest/content/tools/intersect.html</a>)</p>

<p>But this is slow for a large file with &gt;20G in size. Any quick-sorting problem around?</p>

<p>Here is a solution I can think of: </p>

<pre><code>inputbed=$1
awk -v inputbed=$inputbed '{print $0 &gt;&gt; inputbed"."$1}' $inputbed
for i in $inputbed.*; do sort -k2,2n $i &gt; $i.s &amp; done
# when it's done
sort -m -k1,1 -k2,2n $inputbed.*s &gt; $inputbed.sorted
</code></pre>

<p>The basic idea is to split the large file into small files by the first key, then sort each of them by the second key, and finally use "sort -m" to merge the sorted ones. It can save time by parallel sorting individual small file. But you need a way to track when the individual sorting is done.  </p>

<p>I can also read the records into a large hash table, and then sort the key before output. Below is an example of sorting by 1st column (using a hash of hash can sort by two keys):</p>

<pre><code>perl -e 'while (&lt;&gt;) {$l=$_; @a=split("\t", $l); push(@{$HoA{$a[0]}}, $l);}{foreach $i (sort keys %HoA) {print join("", @{$HoA{$i}});}}'
</code></pre>

<p>But again, this method requires large memory. </p>

<p>I am wondering if any quick-sorting program around that you guys can recommend. Thanks</p>

<p><strong>Edit1: Use the parallel sorting from <a href='http://ftp.gnu.org/gnu/coreutils/'>GNU coreutils</a> with "sort --parallel=N" (change the number of sorts run concurrently to N) option. Also set the main buffer size and traditional locale.</strong></p>

<pre><code>LC_ALL=C sort --parallel=24 --buffer-size=5G -k1,1 -k2,2n input.bed &gt; sorted.bed
</code></pre>

<p><strong>Edit2: Use the sort-bed tool from <a href='https://code.google.com/p/bedops/wiki/performance#Independent_evaluations'>BEDOPS</a></strong></p>

<pre><code>sort-bed --max-mem 5G input.bed &gt; sorted.bed
</code></pre>

<p>You might not need to go through the pain of rolling your own.</p>

<p>There are multithreaded sort commands.</p>

<p>have a look @ stackoverflow</p>

<p><a href='http://stackoverflow.com/questions/6365176/multi-threaded-sort'>http://stackoverflow.com/questions/6365176/multi-threaded-sort</a></p>
