在链接列表上自下而上合并排序

Bottom up merge sort treats a list each element of size 1, and iteratively merge the sub-lists back and forth until they are in sorted order. This makes it very attractive to use bottom up merge sort to sort linked list as they are already "separated".

自下而上合并排序处理每个大小为1的元素的列表，并反复合并子列表，直到它们按排序顺序排列。这使得使用自下而上合并排序对链表进行排序非常有吸引力，因为它们已经“分离”了。

I'm trying to implement bottom up merge sort in C language, and realised that there are various approach to implement bottom up merge sort; in particular, I'm using this approach:

我正在尝试用C语言实现自下而上的合并排序，并意识到有各种方法来实现自下而上的合并排序;特别是，我正在使用这种方法：

1. Insert single lists into a queue
2. 将单个列表插入队列
3. Dequeue first two lists and merge them
4. 将前两个列表出列并合并它们
5. Enqueue merged lists (merged items go to the end)
6. 排队合并列表（合并项目结束）
7. Repeat step 1-3 until they are in sorted order
8. 重复步骤1-3，直到它们按排序顺序排列

However, I'm struggling to implement the following:

但是，我正在努力实现以下内容：

• Merge linked-lists without using extra O(n) space (if possible)
• 合并链接列表而不使用额外的O（n）空间（如果可能）

Hence, my questions are:

因此，我的问题是：

• How would one implement this correctly in C language? (in particular: the handling of repeating the dequeue and enqueue process until it's fully sorted) How would one know if the entire queue is in sorted order? I'm thinking of keeping track of the *head pointer(s) in a list.
• 如何在C语言中正确实现这一点？ （特别是：重复出队和排队过程直到完全排序的处理）如何知道整个队列是否按排序顺序？我正在考虑跟踪列表中的*头指针。
• Is merge sort stable in this case? Why?
• 在这种情况下，合并排序是否稳定？为什么？
• The running time of bottom-up merge sort is still O(nlogn). However, does this bottom up merge sort use O(n) space? Suppose the linked-list we implement is already a queue.
• 自下而上合并排序的运行时间仍为O（nlogn）。但是，这个自下而上的合并排序是否使用O（n）空间？假设我们实现的链表已经是一个队列。
• Extra question: is there a better alternative to implement bottom-up merge sort on linked list?
• 额外的问题：是否有更好的替代方法在链表上实现自下而上的合并排序？

I suppose this is one of the advantage of using bottom-up merge sort on linked list, as it is more space efficient than using bottom-up merge sort on arrays. Correct me if I'm wrong.

我认为这是在链表上使用自下而上合并排序的优势之一，因为它比在数组上使用自下而上合并排序更节省空间。如我错了请纠正我。

2 个解决方案

#1

1. How would one implement that? is a bit too broad question, I'm afraid.
2. 如何实现这一点？我害怕是一个有点过于宽泛的问题。
3. Mergesort is stable provided that when you encounter equal items in two sublists, you take them from the 'left' (earlier) sublist first.
4. Mergesort是稳定的，前提是当您在两个子列表中遇到相同的项目时，首先从“左”（早期）子列表中获取它们。
5. With a linked list you can use O(1) space; just unlink sublist sequentially, and append them to a new temporary list after merging, then use the new list in the next iteration with longer sublists. You will only need to keep additional 'head' and 'tail' pointers for a temporary list.
6. 使用链表可以使用O（1）空格;只需按顺序取消链接子列表，并在合并后将它们附加到新的临时列表，然后在下一次迭代中使用具有较长子列表的新列表。您只需要为临时列表保留额外的“头部”和“尾部”指针。
7. Yes, there is: unlink longest possible increasing runs instead of 1, 2, 4... items sublists. That is as good as the original algorithm in the worst case (input in reverse order makes one-item runs in the first iteration), but it makes a full use of an existing partial order if there is one (for a fully sorted input it just scans the list once).
8. 是的，有：取消链接最长可能的增加运行而不是1,2,4 ...项目子列表。这与最坏情况下的原始算法一样好（以相反顺序输入使得在第一次迭代中运行一项），但是如果有一个，则它充分利用现有的部分顺序（对于完全排序的输入它只扫描列表一次）。

#2

There's a clever method that uses a fixed size array (26 or 32 are common sizes) array of pointers to nodes, some working local pointers to nodes, and a standard mergelists() function that merges two already sorted lists, and needs to handle empty lists to make the main code simpler. Nodes are merged into the array, then the array is merged into a single sorted list. The first part of this logic is:

有一个聪明的方法，使用一个固定大小的数组（26或32是常见的大小）指向节点的指针数组，一些工作本地指针指向节点，以及一个标准mergelists（）函数合并两个已经排序的列表，并需要处理空列表使主代码更简单。节点合并到数组中，然后将数组合并到单个排序列表中。这个逻辑的第一部分是：

    // initialize array[] to all NULLs
    while(plist != NULL){
        pmerge = plist;
        plist = plist->next;
        pmerge->next = NULL;
        for(i = 0; i < array size; i++){
            if(array[i] == NULL)
                break;
            pmerge = mergelists(array[i], pmerge);
            array[i] = NULL;
        }
        if(i == array size)i--;
        array[i] = pmerge;
    }

The size of the list doubles as i increases, array[i] is either NULL or points to a list with 2 to the power i nodes.

当i增加时，列表的大小加倍，array [i]为NULL或指向具有2的power i节点的列表。

Then the array is merged into a single list, again with just a loop and a call to mergelists(). See if you can figure out this part.

然后将数组合并到一个列表中，同样只需要一个循环并调用mergelists（）。看看你是否可以弄清楚这一部分。