So I have an enormously large file (around 10GB) and need to sort it, just like in using 'sort' utility, but kindof more effectively.

Problem is, that I don't have memory, CPU power, time, nor free swapping space to power the whole sort.

The good thing is that file is already partially ordered (I can say that every line's distance from its final position is less than some value N). This kindof reminds me the classical computer-class example of using heapsort with heap of size N for this purpose.

Question: Is there some unix tool that already does that effectively, or do I need to code one myself?

Thanks -mk

2 Answers 2


It would be easier to split the file into smaller sections and sort those. To split:-

split --lines=100000 large_file file_part.

Then sort each of those by using normal sort

for suffix in `ls file_part.* | cut -f2 -d.` 
  sort file_part.${suffix} > file_sorted.${suffix} 

you can then combine by merge sorting

sort -m file_sorted.*

That should be much easier on your machine.

  • good idea :] I just need to split the file to lines, but this can be done using splt -l 100000. Thanks
    – exa
    Mar 24, 2011 at 9:47
  • Good point. Answer changed to accomodate lines... Suspect i read the 10Gb and then that put me onto --bytes..
    – Decado
    Mar 24, 2011 at 9:58
  • but you are going to have to do it twice, right? when you have 11211222 and split by every 4 you are going to sort 1121 1222. when you put it back together you have 111212222
    – stew
    Mar 24, 2011 at 11:15
  • @stew. once you've done the split "split --lines=10000 big_file file_part.", you then do a standard sort on each file. so "sort file_part.aa > file.sorted.aa", then you'll merge sort all the parts together "sort -m file.sorted.*". That'll combine them and order correctly. Perhaps the initial sort step wasn't made clear.
    – Decado
    Mar 24, 2011 at 11:25

Sort, is using and R-way merge sort algorithm. The fastest way to do your work would be:

sort myfile

this implies O(n logn ) time complexity and O(n) time .

If you partition the data you will probably pay it in terms of time .

The code above has an issue. The with sort -m the files are not guaranteed to be mutually sorted.

from the unix manual:

   -m, --merge
          merge already sorted files; do not sort


file1: a b c k l q file2: d e m

sort -m file1 file2 

a b c k l q d e m

which is not in sort.

Also the fact that the elements are in places that are less than N does not guarantee a sorted output with the above code:

file : a e b c d h f g

in the file N=3 and all elements are less than 3 places than their proper place

file1: h f g , file2: b c d , file3: a e

sort file1

produces :

file1: f g h , file2: b c d, file3: a e


sorm -m file3 file2 file1


a e b c d f g h

which is wrong.

  • You have that wrong. With your commands sort file1 etc., only the output is sorted, not the real file, since sort writes to stdout by default. If you do a sort -m afterwards, you apply a mergesort to still unsorted files, which does not work, as it expects pre-sorted files. But the sort man page is clearly wrong at this point.
    – Sven
    Mar 24, 2011 at 16:19
  • as per SvenW's statement. Actually doing what i suggest with your values seems to work fine on my machine.
    – Decado
    Mar 24, 2011 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.