Take the 2-minute tour ×
Server Fault is a question and answer site for professional system and network administrators. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 12 down vote accepted

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.` 
do 
  sort file_part.${suffix} > file_sorted.${suffix} 
done

you can then combine by merge sorting

sort -m file_sorted.*

That should be much easier on your machine.

share|improve this answer
    
good idea :] I just need to split the file to lines, but this can be done using splt -l 100000. Thanks –  exa Mar 24 '11 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 '11 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 '11 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 '11 at 11:25
add comment

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

e.g.

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

and

sorm -m file3 file2 file1

outputs:

a e b c d f g h

which is wrong.

share|improve this answer
    
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. –  SvW Mar 24 '11 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 '11 at 16:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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