Sorting two linked lists according to memory location

Question

I need to merge two doubly-linked lists, but not by their values (the lists are not sorted). I want to obtain a single list that has all the nodes from the two, but in the order in which they appear in memory.

Maybe this image helps more: http://img140.imageshack.us/i/drawing2.png/

Is there any algorithm (preferably a fast one) that can do this kind of merge ? Maybe this is a bit helpful:

• the start node of the lists is always before the other ones.
• a list can have up to 8192 nodes.
• I know where the nodes are located in memory because the lists keep track of free location in a big block of memory (used in a memory allocator).
• I work in C++.

Thanks in advance!

Answer 1

"Merge" is a bit misleading here, as you can only merge sorted lists, and yours aren't sorted.

You need to sort, not to merge.

Put the pointers to nodes into a vector. use std::sort on the vector, and pass a comparison functor that casts each pointer to size_t (i think) and compares the resulting numbers.

You can then rearrange your linked lists according to the resulting order in the vector.

Answer 2

Well it sounds like you aren't using std::list, so I'll go with the generic solution. Since your requirement is to merge the lists, but have the nodes be in order of there physical location in memory. You can likely just append the two lists, then sort the nodes by address of the nodes.

see: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html for a sorting algorithm for linked lists.

When sorting, instead of comparing node1->value < node2->value just do (size_t)node1 < (size_t)node2, or something to that nature.