Sort Huge files

[ShaQ.Blogs]

I am trying to understand what techiques can be used to sort really huge files (larger than available memory). I did some googling and came across one technique.

1. Are there any better ways to get this done?

2. Is there some tweaking that can be done to make this itself better?

large enough so that you get a lot of records, but small enough such that it will comfortably fit into memory

3. How do you decide on this value? Consider, memory is 4 GB and currently about 2GB is consumed, and file to sort is 10GB in size. (Consumed memory could of course change dynamically during execution - consumed more/less by other apps.)

[Paul McKenzie]

I am trying to understand what techiques can be used to sort really huge files (larger than available memory).

The technique has been known for decades. It's called an external merge sort:

http://en.wikipedia.org/wiki/External_sorting

That site you found describes nothing more than what has been known and used for the past 40+ years.

Regards,

Paul McKenzie

[GCDEF]

Sounds like it might be time to consider a database.

[monarch_dodra]

I'd say the big question is: "Do you HAVE to use a comparison based sort?".

Depending on the elements being sorted, I'm pretty sure a Bucket/Radix sort can beat the crap out of any sized input.

[ninja9578]

I agree that a radix sort would likely be the best bet here. You do not need to sort things in RAM, you can push large amounts of data off to the hard drive. A Radix sort would be useful here because you can put the buckets on the hard drive, then load small buckets into RAM and do a quicksort on those buckets, then just combine them when you are done iterating each bucket.

[ShaQ.Blogs]

The technique has been known for decades. It's called an external merge sort:

http://en.wikipedia.org/wiki/External_sorting

That site you found describes nothing more than what has been known and used for the past 40+ years.

Thanks for the link & info

I'd say the big question is: "Do you HAVE to use a comparison based sort?".

Depending on the elements being sorted, I'm pretty sure a Bucket/Radix sort can beat the crap out of any sized input.

I agree that a radix sort would likely be the best bet here. You do not need to sort things in RAM, you can push large amounts of data off to the hard drive. A Radix sort would be useful here because you can put the buckets on the hard drive, then load small buckets into RAM and do a quicksort on those buckets, then just combine them when you are done iterating each bucket.

I have some reading to do now...