I have a doubly link-list like this

typedef struct Record
   int i;
   Record* next;
   Record* prev;

I have over 5 trillions of records that I need to handle, now that I need to retrieve all of them and sort them out. If its size was small, I could borrow stl's vector or list to do the job but now that it is too huge, I have no idea how to save the object data before sorting is performed

my function prototype

void sortRec(Record**recToSort,bool bASC){}
  • $\begingroup$ Not sure this is in scope here. $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:01
  • $\begingroup$ Where are the records currently saved? Are they all in memory? In disk? $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:01
  • 1
    $\begingroup$ Use the STXXL if your data doesn't fit into your memory. $\endgroup$ – adrianN Oct 2 '13 at 11:10

You should also have a look at External Sorting algorithms. This is another book on the subject Algorithms and Data Structures for External Memory


Assuming that the records are really stored in the disk, you can use radix sort. Divide you integer into bytes, and start with the lower-order byte. Open 256 new files, and start going over your database in order, sorting the files according to the lower-order byte. Then do it again with the next byte, this time reading your 256 files in order.

If memory is not at a premium, you could always allocate an array - that will actually be more memory-efficient than a linked list. (Why would you use a linked list for such a big array anyhow? The overhead is 200%.)

  • $\begingroup$ Thank you a lot, all records are saved in database and in xml file too $\endgroup$ – Stylin Benjamin Oct 2 '13 at 10:09

You can merge-sort a list in memory.

Let split(a)->(b,c) be a function that splits the list a so that approximately half the number of elements go into b and the rest goes into c. Time for split should be T(n).

Let merge(a,b)->c be a function that merges the two ordered list a and b into an ordered list c. Time for merge should be T(n).

Sorting can then be performed in O(n*log(n)):

def sort(a):
    if len(a) <= 1:
        return a
    b, c = split(a)
    return merge(sort(b), sort(c))

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