Sorting doubly linked list

The traditional sorting algorithm for the list - namely the list - is the MergeSort algorithm, built on the principle of "onion braid" ("pigtail of bulbs"). He perfectly sorts singly-connected lists, and the duplicity of the list does not play any fundamental role in such an algorithm.

The algorithm sorts the list by reassigning the next links between the elements of the list, rather than the physical transfer of useful data from one element to another. Those. All data stored in the list items retains its physical location in memory.

This algorithm is usually implemented in std::list::sort() . For the sake of it, the template std::list given its own sort() method.

The algorithm is simple. It uses the classical algorithm for merging two sorted lists into one sorted list (I will not describe it here, because it is an elementary basic algorithm.)

So:

1. We get K > 0 "hooks" (with numbers from 0 to K-1 ), to which we will hang intermediate sublists. The number K can be arbitrary, its role will become clear from the further description

    List hooks[K] = {}; 

2. Take the first node node from the source list and hang it on the hook 0 , if it is free (initially it will, of course, be free)

    node->next = nullptr; hooks[0] = node; 

3. Take the next node node from the original list and try to hang it on the hook 0 . We immediately see that the hook is busy (i.e., hooks[0] != nullptr ). Then we remove from the hook 0 prev_node node already suspended there earlier. Hook 0 at the same time released)

    prev_node = hooks[0]; hooks[0] = NULL; 

   then we connect nodes node and prev_node to a sorted list of length 2

    if (prev_node->data > node->data) std::swap(prev_node, node); prev_node->next = node; node->next = nullptr; 

   (I wrote out the merge explicitly above, but in fact it can be done by the same sub-algorithm for merging two sorted lists, which I mentioned above and which we will use in such cases below. Just in this case, both merged lists contain one element each. )

   Next, hang this list of length 2 on the hook 1 (if it is free)

    hooks[1] = prev_node; 

4. We continue in the same spirit. We take the next node from the input list and hang it on the hook 0 . We take another regular node from the input list, we see that hook number 0 busy. We merge these nodes into a sorted list of length 2. We try to hang it on the hook number 1 . We see that he is also busy (!). Merge two sorted lists of length 2 into one sorted list of length 4 and hang it on the hook 2 . Hooks 0 and 1 are free.

5. We continue to continue in the same vein. At any time, the hook number k will either be free or busy with a sorted list of length 2 ^k . Each new element from the original list is either hung on a free hook 0 , or it causes a cascade of mergers and outweighs of sublists moving from left to right along the hooks array until a free hook is found. Lists of length 1 are combined into lists of length 2, lists of length 2 - into lists of length 4, lengths of 4 - into 8, etc. etc.

   Of course, the re-cascade should stop if the last element of the hooks array is reached. Those sublists that are able to get to the very last element of the array of hooks , that is, the K-1 hook, merge into one long list and continue to hang on the K-1 hook. Thus, the sublist on the K-1 hook may be longer than 2 ^K-1 .

6. When the source list is fully read and hung on hooks, simply make the final pass through the array of hooks and merge all the sub-lists that are hung on hooks into one final sorted list.

The value of K , as stated above, can be arbitrary. Too small a value of K will not break the algorithm, but will lower its efficiency. It makes sense to choose K approximately equal to log ₂ from the expected number of items in the input lists. It is clear that on a 32-bit platform there is no sense to take K more than 32.

At first glance, it may not seem obvious that this algorithm implements the MergeSort strategy, but if you carefully consider the sequence of splits and merges it performs, you can easily see that the same sublists as in the usual “classic” MergeSort appear in the processing, The order of their processing is somewhat different.

To work with a doubly linked list, you can simply constantly maintain two links prev and next when linking items to each other. However, since this algorithm often links the elements of the list, it may be more reasonable to treat the list as simply connected during the entire algorithm, i.e. support only links next . And at the very end of the algorithm, when the final sorted list is formed (in step 5), set the correct values ​​for the prev links.