I finished redefining the list functions to suit myself, because I couldn’t understand how interfaces with some functions in the code should work, even after the hints in the comments. The new code still works with a doubly linked list, but I renamed list_node_t to node_t and reduced current_list_size to size . There is a function for insertion into the tail, and another for removal from the head; other functions are pretty straight forward.
There are currently three files: the main merge source code ( mergelist.c ), including the main() test program and the revised versions of the three functions in question; a list header ( list.h ) defining an interface to the list_t type; and the source code for the list ( list.c ) implementing the type list_t .
The excitement was mainly related to the main code, but the rest was necessary to make it work. Sort is sorted in descending order (first the highest value). Critical changes (which I remember, except the interface to the list functions) are highlighted in the code for mergelist.c . A key debugging tool was the dump_list() function. Something similar to this is the qua non sine for debugging sorts and lists, etc.
Strictly, type names ending in _t are reserved for implementation (see What does a type followed by _t (underscore t) mean?.
Output example
Compiled with GCC 4.8.1 on Mac OS X 10.8.5, 64-bit pointers.
List Before (0x7FEC21C039A0) Head 0x7FEC21C039C0, Tail 0x7FEC21C03AE0, Size 10 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A20, Data 7 6: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x7FEC21C03A40, Data 5 7: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 8: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 9: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 10: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C039A0) Head 0x7FEC21C039C0, Tail 0x7FEC21C03AE0, Size 10 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A20, Data 7 6: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x7FEC21C03A40, Data 5 7: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 8: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 9: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 10: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B20) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A40, Size 5 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-R (0x7FEC21C03B00) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AE0, Size 5 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 4: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 5: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C03B20) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A40, Size 5 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x7FEC21C03A20, Prev 0x7FEC21C039E0, Data 9 4: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 2 5: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-L (0x7FEC21C03B60) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A00, Size 3 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 9 List Split-R (0x7FEC21C03B40) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A40, Size 2 1: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 2 2: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List -->>list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C039C0, Tail 0x7FEC21C03A00, Size 3 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x7FEC21C03A00, Prev 0x7FEC21C039C0, Data 3 3: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 9 List Split-L (0x7FEC21C03BA0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039E0, Size 2 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 3 List Split-R (0x7FEC21C03B80) Head 0x7FEC21C03A00, Tail 0x7FEC21C03A00, Size 1 1: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x000000000000, Data 9 List -->>list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039E0, Size 2 1: Node 0x7FEC21C039C0, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 1 2: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 3 List Split-L (0x7FEC21C03BE0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039C0, Size 1 1: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x000000000000, Data 1 List Split-R (0x7FEC21C03BC0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039E0, Size 1 1: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x000000000000, Data 3 -->>list_sort_merge() List List-L (0x7FEC21C03BE0) Head 0x7FEC21C039C0, Tail 0x7FEC21C039C0, Size 1 1: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x000000000000, Data 1 List List-R (0x7FEC21C03BC0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039E0, Size 1 1: Node 0x7FEC21C039E0, Next 0x000000000000, Prev 0x000000000000, Data 3 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039C0, Size 2 1: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x000000000000, Data 3 2: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 -->>list_sort_merge() List List-L (0x7FEC21C03BA0) Head 0x7FEC21C039E0, Tail 0x7FEC21C039C0, Size 2 1: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x000000000000, Data 3 2: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List List-R (0x7FEC21C03B80) Head 0x7FEC21C03A00, Tail 0x7FEC21C03A00, Size 1 1: Node 0x7FEC21C03A00, Next 0x000000000000, Prev 0x000000000000, Data 9 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 3 1: Node 0x7FEC21C03A00, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x7FEC21C03A00, Data 3 3: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List -->>list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A40, Size 2 1: Node 0x7FEC21C03A20, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 2 2: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 7 List Split-L (0x7FEC21C03B80) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A20, Size 1 1: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x000000000000, Data 2 List Split-R (0x7FEC21C03BA0) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A40, Size 1 1: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x000000000000, Data 7 -->>list_sort_merge() List List-L (0x7FEC21C03B80) Head 0x7FEC21C03A20, Tail 0x7FEC21C03A20, Size 1 1: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x000000000000, Data 2 List List-R (0x7FEC21C03BA0) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A40, Size 1 1: Node 0x7FEC21C03A40, Next 0x000000000000, Prev 0x000000000000, Data 7 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A20, Size 2 1: Node 0x7FEC21C03A40, Next 0x7FEC21C03A20, Prev 0x000000000000, Data 7 2: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x7FEC21C03A40, Data 2 -->>list_sort_merge() List List-L (0x7FEC21C03B60) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 3 1: Node 0x7FEC21C03A00, Next 0x7FEC21C039E0, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C039E0, Next 0x7FEC21C039C0, Prev 0x7FEC21C03A00, Data 3 3: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C039E0, Data 1 List List-R (0x7FEC21C03B40) Head 0x7FEC21C03A40, Tail 0x7FEC21C03A20, Size 2 1: Node 0x7FEC21C03A40, Next 0x7FEC21C03A20, Prev 0x000000000000, Data 7 2: Node 0x7FEC21C03A20, Next 0x000000000000, Prev 0x7FEC21C03A40, Data 2 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B20) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 5 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A40, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A00, Data 7 3: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03A40, Data 3 4: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 5: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 1 List -->>list_sort_merge() (0x7FEC21C03B00) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AE0, Size 5 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A80, Data 6 4: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 0 5: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B40) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AA0, Size 3 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 6 List Split-R (0x7FEC21C03B60) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AE0, Size 2 1: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x000000000000, Data 0 2: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List -->>list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A60, Tail 0x7FEC21C03AA0, Size 3 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A60, Data 8 3: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 6 List Split-L (0x7FEC21C03BA0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A80, Size 2 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x7FEC21C03A60, Data 8 List Split-R (0x7FEC21C03B80) Head 0x7FEC21C03AA0, Tail 0x7FEC21C03AA0, Size 1 1: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x000000000000, Data 6 List -->>list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A80, Size 2 1: Node 0x7FEC21C03A60, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 5 2: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x7FEC21C03A60, Data 8 List Split-L (0x7FEC21C03BE0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A60, Size 1 1: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x000000000000, Data 5 List Split-R (0x7FEC21C03BC0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A80, Size 1 1: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x000000000000, Data 8 -->>list_sort_merge() List List-L (0x7FEC21C03BE0) Head 0x7FEC21C03A60, Tail 0x7FEC21C03A60, Size 1 1: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x000000000000, Data 5 List List-R (0x7FEC21C03BC0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A80, Size 1 1: Node 0x7FEC21C03A80, Next 0x000000000000, Prev 0x000000000000, Data 8 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03BA0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 2 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03A60, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 5 -->>list_sort_merge() List List-L (0x7FEC21C03BA0) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 2 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03A60, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03A80, Data 5 List List-R (0x7FEC21C03B80) Head 0x7FEC21C03AA0, Tail 0x7FEC21C03AA0, Size 1 1: Node 0x7FEC21C03AA0, Next 0x000000000000, Prev 0x000000000000, Data 6 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B40) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 3 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03AA0, Data 5 List -->>list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AE0, Size 2 1: Node 0x7FEC21C03AC0, Next 0x7FEC21C03AE0, Prev 0x000000000000, Data 0 2: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x7FEC21C03AC0, Data 4 List Split-L (0x7FEC21C03B80) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AC0, Size 1 1: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x000000000000, Data 0 List Split-R (0x7FEC21C03BA0) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AE0, Size 1 1: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x000000000000, Data 4 -->>list_sort_merge() List List-L (0x7FEC21C03B80) Head 0x7FEC21C03AC0, Tail 0x7FEC21C03AC0, Size 1 1: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x000000000000, Data 0 List List-R (0x7FEC21C03BA0) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AE0, Size 1 1: Node 0x7FEC21C03AE0, Next 0x000000000000, Prev 0x000000000000, Data 4 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B60) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AC0, Size 2 1: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x000000000000, Data 4 2: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 -->>list_sort_merge() List List-L (0x7FEC21C03B40) Head 0x7FEC21C03A80, Tail 0x7FEC21C03A60, Size 3 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x000000000000, Prev 0x7FEC21C03AA0, Data 5 List List-R (0x7FEC21C03B60) Head 0x7FEC21C03AE0, Tail 0x7FEC21C03AC0, Size 2 1: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x000000000000, Data 4 2: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C03B00) Head 0x7FEC21C03A80, Tail 0x7FEC21C03AC0, Size 5 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 4: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A60, Data 4 5: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 -->>list_sort_merge() List List-L (0x7FEC21C03B20) Head 0x7FEC21C03A00, Tail 0x7FEC21C039C0, Size 5 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A40, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A40, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A00, Data 7 3: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03A40, Data 3 4: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 5: Node 0x7FEC21C039C0, Next 0x000000000000, Prev 0x7FEC21C03A20, Data 1 List List-R (0x7FEC21C03B00) Head 0x7FEC21C03A80, Tail 0x7FEC21C03AC0, Size 5 1: Node 0x7FEC21C03A80, Next 0x7FEC21C03AA0, Prev 0x000000000000, Data 8 2: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A80, Data 6 3: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 4: Node 0x7FEC21C03AE0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A60, Data 4 5: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C03AE0, Data 0 <<--list_sort_merge() List <<--list_sort_merge() (0x7FEC21C039A0) Head 0x7FEC21C03A00, Tail 0x7FEC21C03AC0, Size 10 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 8 3: Node 0x7FEC21C03A40, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A80, Data 7 4: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A40, Data 6 5: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 6: Node 0x7FEC21C03AE0, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A60, Data 4 7: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03AE0, Data 3 8: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 9: Node 0x7FEC21C039C0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A20, Data 1 10: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 0 List After (0x7FEC21C039A0) Head 0x7FEC21C03A00, Tail 0x7FEC21C03AC0, Size 10 1: Node 0x7FEC21C03A00, Next 0x7FEC21C03A80, Prev 0x000000000000, Data 9 2: Node 0x7FEC21C03A80, Next 0x7FEC21C03A40, Prev 0x7FEC21C03A00, Data 8 3: Node 0x7FEC21C03A40, Next 0x7FEC21C03AA0, Prev 0x7FEC21C03A80, Data 7 4: Node 0x7FEC21C03AA0, Next 0x7FEC21C03A60, Prev 0x7FEC21C03A40, Data 6 5: Node 0x7FEC21C03A60, Next 0x7FEC21C03AE0, Prev 0x7FEC21C03AA0, Data 5 6: Node 0x7FEC21C03AE0, Next 0x7FEC21C039E0, Prev 0x7FEC21C03A60, Data 4 7: Node 0x7FEC21C039E0, Next 0x7FEC21C03A20, Prev 0x7FEC21C03AE0, Data 3 8: Node 0x7FEC21C03A20, Next 0x7FEC21C039C0, Prev 0x7FEC21C039E0, Data 2 9: Node 0x7FEC21C039C0, Next 0x7FEC21C03AC0, Prev 0x7FEC21C03A20, Data 1 10: Node 0x7FEC21C03AC0, Next 0x000000000000, Prev 0x7FEC21C039C0, Data 0
mergelist.c
The biggest problem with splitlist() was that the lists were not completely split. If you tracked the left list, you also went through the correct list. This can lead to problems - in fact, many problems.
#include "list.h" #include <assert.h> static void mergelist(list_t *list_ptr, list_t *left_list, list_t *right_list); static void splitlist(list_t *list_ptr, list_t *left_list, list_t *right_list); static int comp_proc(data_t d1, data_t d2) { if (d1 > d2) return +1; else if (d1 < d2) return -1; else return 0; } void list_sort_merge(list_t *list_ptr) { if (list_ptr->size > 1) // 1, not 0 — do not try splitting a singleton list. { dump_list(stdout, "-->>list_sort_merge()", list_ptr); // Debug list_t *right_list = list_construct(); list_t *left_list = list_construct(); splitlist(list_ptr, left_list, right_list); dump_list(stdout, "Split-L", left_list); // Debug dump_list(stdout, "Split-R", right_list); // Debug list_sort_merge(left_list); list_sort_merge(right_list); dump_list(stdout, "Sort-L", left_list); // Debug dump_list(stdout, "Sort-R", right_list); // Debug list_ptr->head = NULL; list_ptr->tail = NULL; list_ptr->size = 0; // Additional mergelist(list_ptr, left_list, right_list); list_destruct(right_list); list_destruct(left_list); dump_list(stdout, "<<--list_sort_merge()", list_ptr); // Debug } } static void mergelist(list_t *list_ptr, list_t *left_list, list_t *right_list) { node_t *holder; fprintf(stdout, "-->>list_sort_merge()\n"); dump_list(stdout, "List-L", left_list); dump_list(stdout, "List-R", right_list); while (left_list->size > 0 && right_list->size > 0) { assert(left_list->head != 0 && right_list->head != 0); /* Sort into descending order */ if (comp_proc(left_list->head->data, right_list->head->data) > 0) { holder = list_remove_head(left_list); list_insert_tail(list_ptr, holder); } else { holder = list_remove_head(right_list); list_insert_tail(list_ptr, holder); } } while (left_list->size > 0) { holder = list_remove_head(left_list); list_insert_tail(list_ptr, holder); } while (right_list->size > 0) { holder = list_remove_head(right_list); list_insert_tail(list_ptr, holder); } fprintf(stdout, "<<--list_sort_merge()\n"); } static void splitlist(list_t *list_ptr, list_t *left_list, list_t *right_list) { if (list_ptr->size > 1) { size_t temp = 0; node_t *holder = list_ptr->head; right_list->size = list_ptr->size / 2; left_list->size = list_ptr->size - right_list->size; left_list->head = list_ptr->head; right_list->tail = list_ptr->tail; while (temp < left_list->size) { temp++; holder = holder->next; } /* Make sure the two lists are separate — a major issue */ right_list->head = holder; left_list->tail = holder->prev; left_list->tail->next = NULL; left_list->head->prev = NULL; right_list->tail->next = NULL; right_list->head->prev = NULL; } } int main(void) { int values[] = { 1, 3, 9, 2, 7, 5, 8, 6, 0, 4 }; enum { NUM_VALUES = sizeof(values)/sizeof(values[0]) }; list_t *list = list_construct(); //dump_list(stdout, "Empty list", list); for (size_t i = 0; i < NUM_VALUES; i++) { node_t *node = node_construct(values[i]); list_insert_tail(list, node); //dump_list(stdout, "Inserting", list); } dump_list(stdout, "Before", list); list_sort_merge(list); dump_list(stdout, "After", list); list_destruct(list); return 0; }
list.h
#ifndef LIST_H_INCLUDED #define LIST_H_INCLUDED #include <stdio.h> typedef int data_t; typedef struct node_t node_t; struct node_t { node_t *next; node_t *prev; data_t data; }; typedef struct list_t list_t; struct list_t { node_t *head; node_t *tail; size_t size; }; extern node_t *node_construct(data_t data); extern void node_destruct(node_t *node); extern size_t list_size(list_t *list); extern void list_insert_tail(list_t *list, node_t *node); extern node_t *list_remove_head(list_t *list); extern void list_destruct(list_t *list); extern list_t *list_construct(void); extern void dump_list(FILE *fp, const char *tag, list_t *list); extern void list_sort_merge(list_t *list_ptr); #endif /* LIST_H_INCLUDED */
list.c
#include "list.h" #include <assert.h> #include <inttypes.h> #include <stdlib.h> extern node_t *list_head(list_t *list); extern node_t *list_tail(list_t *list); extern void list_destruct(list_t *list); extern list_t *list_construct(void); size_t list_size(list_t *list) { return list->size; } void list_insert_tail(list_t *list, node_t *node) { assert(list != 0); assert(node != 0); if (list->tail == 0) { assert(list->tail == 0 && list->head == 0 && list->size == 0); list->tail = node; list->head = node; node->prev = 0; node->next = 0; list->size = 1; } else { list->tail->next = node; node->prev = list->tail; node->next = 0; list->size++; list->tail = node; } } node_t *list_remove_head(list_t *list) { assert(list != 0); node_t *node = list->head; if (list->head != 0) { assert(list->size > 0); list->head = node->next; if (node->next != 0) node->next->prev = 0; node->prev = 0; node->next = 0; list->size--; } return node; } void list_destruct(list_t *list) { assert(list != 0); node_t *next; for (node_t *node = list->head; node != 0; node = next) { next = node->next; node_destruct(node); } free(list); } void dump_list(FILE *fp, const char *tag, list_t *list) { assert(list != 0); fprintf(fp, "List %s (0x%.12" PRIXPTR ")\n", tag, (uintptr_t)list); fprintf(fp, "Head 0x%.12" PRIXPTR ", Tail 0x%.12" PRIXPTR ", Size %zu\n", (uintptr_t)list->head, (uintptr_t)list->tail, list->size); size_t i = 0; for (node_t *node = list->head; node != 0; node = node->next) fprintf(fp, "%2zu: Node 0x%.12" PRIXPTR ", Next 0x%.12" PRIXPTR ", Prev 0x%.12" PRIXPTR ", Data %d\n", ++i, (uintptr_t)node, (uintptr_t)node->next, (uintptr_t)node->prev, node->data); } list_t *list_construct(void) { list_t *list = malloc(sizeof(*list)); if (list != 0) { list->head = 0; list->tail = 0; list->size = 0; } return list; } node_t *node_construct(data_t data) { node_t *node = malloc(sizeof(*node)); if (node != 0) { node->data = data; node->next = 0; node->prev = 0; } return node; } void node_destruct(node_t *node) { free(node); }