Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am looking for sorting algorithms that can work on a large amount of data, i.e. that can work even when the whole data set cannot be held in main memory at once.

The only candidate that I have found up to now is merge sort: you can implement the algorithm in such a way that it scans your data set at each merge without holding all the data in main memory at once. The variation of merge sort I have in mind is described in this article in section Use with tape drives.

I think this is a good solution (with complexity O(n x log(n)) but I am curious to know if there are other (possibly faster) sorting algorithms that can work on large data sets that do not fit in main memory.

EDIT

Here are some more details, as required by the answers:

  • The data needs to be sorted periodically, e.g. once in a month. I do not need to insert a few records and have the data sorted incrementally.
  • My example text file is about 1 GB UTF-8 text, but I wanted to solve the problem in general, even if the file were, say, 20 GB.
  • It is not in a database and, due to other constraints, it cannot be.
  • The data is dumped by others as a text file, I have my own code to read this text file.
  • The format of the data is a text file: new line characters are record separators.

One possible improvement I had in mind was to split the file into files that are small enough to be sorted in memory, and finally merge all these files using the algorithm I have described above.

share|improve this question
1  
What kind of data? Different data sets can mean different algorithms that best suit your purpose. –  whatsisname Jan 3 '12 at 15:31
    
It is a text file and I have to sort the lines. Lines are not fixed length but the length does not vary too much (around 50 characters per record). –  Giorgio Jan 3 '12 at 16:21
3  
I don't know your environment or your constraints, but I would use a database for sorting whenever possible. This is because it is almost 100% error-proof and will be much more efficient than my code. –  Emmad Kareem Jan 3 '12 at 16:59
    
I am working on Linux / Java. I have implemented merge sort and it seems to work quite smoothly. Sorting several million lines takes quite some time but I only need to do this once in a while. –  Giorgio Jan 3 '12 at 17:08
    
@Giorgio, it is good that you have implemented such an algorithm. For production work, I still suggest that you use a database. Not only for speed but also for reliability and ease of maintenance. –  Emmad Kareem Jan 3 '12 at 17:14

8 Answers 8

up vote 10 down vote accepted

The canonical reference on sorting and searching is Knuth, Vol. 3. Start there.

The book was originally written back when computers were a lot smaller and slower than they are now, which made out-of-memory sorting techniques more important than they are perceived to be today.

share|improve this answer
2  
Thanks for the reference: I am almost sure that I will find interesting material in Knuth's book. I am not sure that out-of-memory sorting techniques are not relevant today. Maybe not for common, every-day tasks, but I can imagine that there are still lots of situations in which very large data sets need to be processed. –  Giorgio Jan 3 '12 at 19:34
    
Knuth's algorithms are always helpful. For example a merging sort with a heap-sort buffer can be very effective and VERY easy to implement. –  Sulthan May 29 '13 at 10:53
1  
Not a very useful answer because the referred material is not free. For the OP, I suggest googling for an answer. You don't need to shell $50 bucks to get a book when this kind of information you can find by digging around the web. Of course, you can probably download this for free from (ahem) certain sites as well. Hardly deserving of an accepted answer. –  Thomas Eding Oct 15 '13 at 16:50

External R-Way merge as in the UNIX sort command is a good alternative. From your formulation, I'm not sure if that is the algorithm you meant with "merge sort", and if you don't know it, have a look.

share|improve this answer
    
Thanks. External R-Way merge seems different from what I had in mind. Interesting reading. –  Giorgio Jan 3 '12 at 15:16

Without more specifics "Merge Sort" is probably the best answer you will get, however you can implement something much smarter depending on your requirements.

For instance, can you simply create an in-memory index of the file then copy all the values at once, caching the location of various key values? Does 1/2 fit in memory at once, or 1/1000000? If it's the second one then you might not be able to fit an index in memory, if the first then you could sort both halves more efficiently then merge them together in a single last step.

Hell, since you didn't specify it it's possible that your data is all in a database, if so you can just create an index table and call it good (I'm guessing this isn't the case, but just pointing out that your situation is critical to resolving a complicated problem like this).

If you want to do it just once and are looking for a very quick hack it sounds like that external merge sort would be a good start if you are running unix (since it's apparently built in)

If you have to keep it in order and are always adding a single record then an insertion sort will be necessary (Adding a single record to sorted data is always an insertion sort).

Can you control the code that "Reads" the data? If so then many forms of indexing (rather than sorting by moving data around on the disk) will help A LOT (will actually be an absolute requirement).

So:

  • In place or multiple file?
  • One time, periodical or keep it sorted at all times?
  • How much bigger than memory (How many memory-loads to get through the entire data set)?
  • Is it in a database? Can it be?
  • Do you control the code that reads the data, or will others be dumping a file directly?
  • File format? (Text? Fixed record?)
  • Any other special circumstances I didn't ask about?
share|improve this answer
    
Thanks for the answer. What do you mean by "In place or multiple record"? –  Giorgio Jan 3 '12 at 17:14
    
Sorry, should have proof-read my answer--I meant multiple file. In-place pretty much implies fixed record sizes and indexing at which point you would probably want a database. –  Bill K Jan 3 '12 at 17:46
    
No it is not in place: records are not fixed size. I use four temporary files for my current implementation. –  Giorgio Jan 3 '12 at 17:47
    
Can you interpret the output with code or does it have to be in a specific format (flat text file?) How often does it need to be sorted--every time something is added or just occasionally? When something is added is it just appended to the end or can you write the code that adds it? –  Bill K Jan 3 '12 at 20:02
    
Each line can be parsed into a record (the file is a CSV file) but most of the fields are text. It needs to be sorted once in a while (e.g. every month) and it takes about 1 hour to sort with my current implementation. For inserting a line I could write the code that inserts the line at the right place: with the code I have so far it would take me 20 minutes to write such a tool. –  Giorgio Jan 3 '12 at 20:06

If you really want a scalable solution you should take a look at TeraSort, the standard sort implementation with map-reduce; more details on StackOverflow.

share|improve this answer
1  
+1: Interesting link. Isn't merge sort an example of map / reduce, where map corresponds to sorting sub-lists, and reduce corresponds to merging? –  Giorgio Nov 1 '12 at 8:41
    
It may be seen so, but you can use Hadoop for doing this for you instead of writing it yourself. –  m3th0dman Nov 1 '12 at 8:46

You might be interested in a bucket sort. The average case performance is linear time.

= O(n+d) n: number of elements and d = length of largest number if you have an intuition about your data ie. If you know how many 'digits' long is your largest number. So if you have 2 million 6 digit numbers => 0(n) thus linear.

share|improve this answer

Use external merge sort algorithm (if your data are continuos), or a bucket sort with counting sort as a implementation of sorting for buckets (if your data are discrete and uniformly distributed).

Probably the best approach is to build your own index/mapping file if the increment is small.

  1. Somehow order your "database"
  2. Assign an integer to every entry (1, 2, 3, 4, ..., n) (better: use some sparse indexes)
  3. When adding an increment just find a gap where the left number is less or equal and the right number is greater or equal (it should not be difficult with some modified version of a binary search)
  4. Insert, while the gaps are sufficietly big, if not: just reindex (never sort again) :-)
share|improve this answer

I have just built some abstract structures called big queue and big array to simplify big data sorting and searching task on a single machine with limited memory. Basically, the algorithm used is similar to the one you mentioned above - external merge sort.

I can sort 128GB data(each item 100 bytes) in 9 hours on a single machine, and then binary search the sorted data with almost no time.

Here is a post about how to search big data by using my open source big queue and big array structures.

share|improve this answer

Are you trying to solve a problem or are you trying to write a sorting algorithm? It might not seem like there is a difference between the two, but there is a big difference.

If you are looking for a sorting algorithm then there are several sorting algorithms that can be adapted to sort data that are too large to fit in memory, but just be aware of performance when you are continuously swapping in and out of memory.

If you are looking to get data sorted and do not care about method, then instead of an algorithm, you could just use tables (temp tables or even some types of files) as a way of sorting data that can be very effective when working with large amounts of data and also when wanting to sort on more than one field.

share|improve this answer
1  
Hi and welcome to programmers.SE - can you elaborate on your answer? The OP asked about sorting algorithms, but you answered with an implementation approach. Try explaining the algorithm behind temp-tables and how this can help solve the question at the top. –  Rafael Cichocki May 29 '13 at 10:39

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.