使用归并排序来排序链表。

I am currently working on the mergesort algorithm. I have three functions. list_sort_merge, mergelist and splitlist. list_sort_merge calls the other two to split and merge the list. I am having trouble getting this to work correctly. So what happens when I run GDB is that I get through the split function and get each number by itself such as the following example:

我目前正在研究归并排序算法。我有三个功能。list_sort_merge,mergelist splitlist。list_sort_merge调用其他两个来拆分和合并列表。我很难让它正常工作。当我运行GDB时，我通过拆分函数得到每个数，比如下面的例子:

427
42.7
4.2.7

Then the mergesort comes along and segfaults me. What happens is the right_list and left_list are not being passed to mergesort. Meaning when mergesort goes to compare in the function comp_proc, it says that they are both NULL.

然后归并排序就出现了，并把我分割了。发生的情况是，right_list和left_list不会被传递到mergesort。当mergesort在函数comp_proc中进行比较时，它表示它们都是NULL。

I think the problem is coming from the split function.

我认为问题来自于分裂函数。

Can anyone see what I am doing wrong here?

有人能看出我做错了什么吗?

2 个解决方案

#1

I ended up reimplementing the list functions to suit myself because I couldn't work out how the interfaces to some of the functions in the code were supposed to work, even after the hints in the comments. The new code is still working with a doubly-linked list, but I renamed list_node_t to node_t and shortened current_list_size to size. There's a function to insert at the tail, and another to remove from the head; the other functions are fairly straight-forward.

我最终重新实现了列表函数，以适合自己，因为我无法计算出代码中某些函数的接口是如何工作的，即使在注释的提示之后。新代码仍在使用双链表，但我将list_node_t重命名为node_t，并将current_list_size缩短为size。有一个函数可以插入到尾部，另一个可以从头部移开;其他函数是相当直接的。

There are now three files: the main merge-sort source code (mergelist.c), including a test main() program and the revised versions of the three functions in the question; the list header (list.h) defining the interface to the list_t type; and the list source code (list.c) implementing the list_t type.

现在有三个文件:主要的merge-sort源代码(mergelist.c)，其中包括一个测试main()程序和这个问题中的三个函数的修改版本;将接口定义为list_t类型的列表头(list.h);以及实现list_t类型的列表源代码(list.c)。

The excitement is mostly in the main code, but the rest was necessary to get things to work. The sort sorts in descending order (largest value first). The crucial changes (that I recall, and other than the interface to the list functions) are highlighted in the code for mergelist.c. The key debugging tool was the dump_list() function. Something similar to that is a sine qua non for debugging sorts and lists and so on.

这种兴奋主要集中在主要代码中，但是其余的部分都是需要工作的。排序按降序排序(最大值优先)。在mergelist.c的代码中突出显示了关键的更改(我记得，而不是列表函数的接口)。关键的调试工具是dump_list()函数。与此类似的是用于调试排序和列表的sinqua。

Strictly, type names ending in _t are reserved for the implementation (see What does a type followed by _t (underscore t) represent?).

严格地说，在_t中结束的类型名称是为实现保留的(请参见后面的类型为_t(下划线t)表示什么?)

Sample output

Compiled with GCC 4.8.1 on Mac OS X 10.8.5, 64-bit pointers.

在Mac OS X 10.8.5, 64位指针上编译了GCC 4.8.1。

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 in splitlist() was that the lists were not cleanly severed. If you tracked down the left list, you traversed the right list too. This could lead to problems — lots of problems, in fact.

splitlist()中最大的问题是列表没有被干净地切断。如果你找到了左边的列表，你也会遍历右边的列表。这可能会导致问题——事实上，很多问题。

#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);
}

#2

Here is an explanation: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

这里有一个解释:http://www.chiark.greenend.org.uk/~sgtatham/算法/listsort.html。

and the example code: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c

以及示例代码:http://www.chiark.greenend.org.uk/~sgtatham/算法/listsort.c。