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.


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.

  • 1
    What kind of data? Different data sets can mean different algorithms that best suit your purpose. Commented Jan 3, 2012 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
    Commented Jan 3, 2012 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.
    – NoChance
    Commented Jan 3, 2012 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
    Commented Jan 3, 2012 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.
    – NoChance
    Commented Jan 3, 2012 at 17:14

7 Answers 7


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.

  • 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
    Commented Jan 3, 2012 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
    Commented May 29, 2013 at 10:53
  • 4
    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. Commented Oct 15, 2013 at 16:50
  • 2
    @ThomasEding, there are these things called "libraries", that contain large quantities of these obsolete information storage and retrieval devices called "books". "Libraries" make "books" available for FREE LOAN. If your particular "library" does not have the particular "book" you seek, they also offer a FREE service called "interlibrary loan", which allows the "library" to borrow the "book" from another "library", so they can loan it to you. Commented Oct 6, 2016 at 14:56

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.

  • Thanks. External R-Way merge seems different from what I had in mind. Interesting reading.
    – Giorgio
    Commented Jan 3, 2012 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).


  • 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?
  • Thanks for the answer. What do you mean by "In place or multiple record"?
    – Giorgio
    Commented Jan 3, 2012 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
    Commented Jan 3, 2012 at 17:46
  • No it is not in place: records are not fixed size. I use four temporary files for my current implementation.
    – Giorgio
    Commented Jan 3, 2012 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
    Commented Jan 3, 2012 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
    Commented Jan 3, 2012 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.

  • 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
    Commented Nov 1, 2012 at 8:41
  • It may be seen so, but you can use Hadoop for doing this for you instead of writing it yourself.
    – Random42
    Commented Nov 1, 2012 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.


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) :-)

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.

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