合并排序链接列表

Question

我最近复习了一些基础知识，发现对链表进行合并排序是一个很好的挑战。 如果您有一个好的实现，请在这里展示。

Answer 1

很大程度上基于以下优秀代码：http://www.chiark。 greenend.org.uk/~sgtatham/algorithms/listsort.html

稍微修剪并整理：

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list;  // Trivial case

    do { // For each power of two<=list length
        numMerges=0,left=list;tail=list=0; // Start at the start

        while (left) { // Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
            // Cut list into two halves (but don't overrun)
            while (right && leftSize<listSize) leftSize++,right=right->next;
            // Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
                // Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
                // Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
                // Sort prev pointer
                next->prev=tail; // Optional.
                tail=next;          
            }
            // Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
        // Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
    return list;
}

注意：这是 O(NLog(N)) 保证，并且使用 O(1) 资源（无递归，无堆栈） ， 没有什么）。

Answer 2

public int[] msort(int[] a) {
    if (a.Length > 1) {
        int min = a.Length / 2;
        int max = min;

        int[] b = new int[min];
        int[] c = new int[max]; // dividing main array into two half arrays
        for (int i = 0; i < min; i++) {
            b[i] = a[i];
        }

        for (int i = min; i < min + max; i++) {
            c[i - min] = a[i];
        }

        b = msort(b);
        c = msort(c);

        int x = 0;
        int y = 0;
        int z = 0;

        while (b.Length != y && c.Length != z) {
            if (b[y] < c[z]) {
                a[x] = b[y];
                //r--
                x++;
                y++;
            } else {
                a[x] = c[z];
                x++;
                z++;
            }
        }

        while (b.Length != y) {
            a[x] = b[y];
            x++;
            y++;
        }

        while (c.Length != z) {
            a[x] = c[z];
            x++;
            z++;
        }
    }

    return a;
}

Answer 3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0)
            return null;

        List<Integer> list = new ArrayList<>();
        
        for(int i = 0; i < lists.length; i++){
            ListNode listNode = lists[i];
            while(listNode != null){
                list.add(listNode.val);
                listNode = listNode.next;
            }
        }
        if(list.size() == 0)
            return null;

        Collections.sort(list);
        ListNode result = new ListNode(list.remove(0));
        list.forEach(v -> doAdd(v, result));
        return result;
    }

    private void doAdd(int val, ListNode node){
        if(node.next == null){
            node.next = new ListNode(val);
            return;
        }
        doAdd(val, node.next);
    }
}

Answer 4

这是使用Swift 编程语言的解决方案。

//Main MergeSort Function
func mergeSort(head: Node?) -> Node? {
   guard let head = head else { return nil }
   guard let _ = head.next else { return head }

   let middle = getMiddle(head: head)
   let left = head
   let right = middle.next

   middle.next = nil

   return merge(left: mergeSort(head: left), right: mergeSort(head: right))
}

//Merge Function
func merge(left: Node?, right: Node?) -> Node? {

   guard let left = left, let right = right else { return nil}

   let dummyHead: Node = Node(value: 0)

   var current: Node? = dummyHead
   var currentLeft: Node? = left
   var currentRight: Node? = right

   while currentLeft != nil && currentRight != nil {
       if currentLeft!.value < currentRight!.value {
        current?.next = currentLeft
        currentLeft = currentLeft!.next
       } else {
        current?.next = currentRight
        currentRight = currentRight!.next
       }
       current = current?.next
   }


   if currentLeft != nil {
        current?.next = currentLeft
   }

   if currentRight != nil {
        current?.next = currentRight
   }

   return dummyHead.next!
}

这里是节点类 & getMiddle方法

class Node { 
    //Node Class which takes Integers as value
    var value: Int
    var next: Node?
    
    init(value: Int) {
        self.value = value
    }
}

func getMiddle(head: Node) -> Node {
    guard let nextNode = head.next else { return head }
    
    var slow: Node = head
    var fast: Node? = head
    
    while fast?.next?.next != nil {
        slow = slow.next!
        fast = fast!.next?.next
    }
    
    
    return slow
}

Answer 5

嘿，我知道这个答案有点晚了，但得到了一个快速简单的答案。

代码采用 F# 语言，但适用于任何语言。 由于这是 ML 家族中不常见的语言，因此我将给出一些要点来增强可读性。
F# 是通过制表完成嵌套的。 函数中的最后一行代码（嵌套部分）是返回值。 (x,y)是一个元组，x::xs是头x和尾xs的列表（其中xs可以为空），|> 将最后一行的结果通过管道作为其右侧表达式的参数（增强可读性），最后一个 (fun args -> some expression) 是一个 lambda 函数。

// split the list into a singleton list
let split list = List.map (fun x -> [x]) lst

// takes to list and merge them into a sorted list
let sort lst1 lst2 =
   // nested function to hide accumulator
   let rec s acc pair =
       match pair with
       // empty list case, return the sorted list
       | [], [] -> List.rev acc
       | xs, [] | [], xs ->
          // one empty list case, 
          // append the rest of xs onto acc and return the sorted list
          List.fold (fun ys y -> y :: ys) acc xs
          |> List.rev
       // general case
       | x::xs, y::ys ->
          match x < y with
          | true -> // cons x onto the accumulator
              s (x::acc) (xs,y::ys)
          | _ ->
              // cons y onto the accumulator
              s (y::acc) (x::xs,ys)

    s [] (lst1, lst2)  

let msort lst =
  let rec merge acc lst =
      match lst with
      | [] ->
          match acc with
          | [] -> [] // empty list case
          | _ -> merge [] acc
      | x :: [] -> // single list case (x is a list)
         match acc with
         | [] -> x // since acc are empty there are only x left, hence x are the sorted list.
         | _ -> merge [] (x::acc) // still need merging.
       | x1 :: x2 :: xs ->
           // merge the lists x1 and x2 and add them to the acummulator. recursiv call
           merge (sort x1 x2 :: acc) xs

   // return part
   split list // expand to singleton list list
   |> merge [] // merge and sort recursively.

重要的是要注意，这是完全尾递归的，因此不存在堆栈溢出的可能性，并且通过首先将列表一次性扩展为单例列表，我们降低了最差成本的常数因子。 由于合并是在列表的列表上进行的，因此我们可以递归地合并和排序内部列表，直到到达所有内部列表都被排序到一个列表的固定点，然后我们返回该列表，从而从列表列表折叠为列表再次。

Answer 6

下面是链表归并排序的 Java 实现：

• 时间复杂度：O(n.logn)
• 空间复杂度：O(1) - 链表上的合并排序实现避免了通常与
  算法

class Solution
{
    public ListNode mergeSortList(ListNode head) 
    {
        if(head == null || head.next == null)
            return head;

        ListNode mid = getMid(head), second_head = mid.next; mid.next = null;

        return merge(mergeSortList(head), mergeSortList(second_head));
    }

    private ListNode merge(ListNode head1, ListNode head2)
    {
        ListNode result = new ListNode(0), current = result;

        while(head1 != null && head2 != null)
        {
            if(head1.val < head2.val)
            {
                current.next = head1;
                head1 = head1.next;
            }
            else
            {
                current.next = head2;
                head2 = head2.next;
            }
            current = current.next;
        }

        if(head1 != null) current.next = head1;
        if(head2 != null) current.next = head2;

        return result.next;
    }

    private ListNode getMid(ListNode head)
    {
        ListNode slow = head, fast = head.next;

        while(fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Answer 7

我没有看到这里发布任何 C++ 解决方案。 那么，就这样吧。 希望它能帮助某人。

class Solution {
public:
    ListNode *merge(ListNode *left, ListNode *right){
        ListNode *head = NULL, *temp = NULL;
        // Find which one is the head node for the merged list
        if(left->val <= right->val){
            head = left, temp = left;
            left = left->next;
        }
        else{
            head = right, temp = right;
            right = right->next;
        }
        while(left && right){
            if(left->val <= right->val){
                temp->next = left;
                temp = left;
                left = left->next;
            }
            else{
                temp->next = right;
                temp = right;
                right = right->next;
            }
        }
        // If some elements still left in the left or the right list
        if(left)
            temp->next = left;
        if(right)
            temp->next = right;
        return head;
    }

    ListNode* sortList(ListNode* head){
        if(!head || !head->next)
            return head;

        // Find the length of the list
        int length = 0;
        ListNode *temp = head;
        while(temp){
            length++;
            temp = temp->next;
        }
        // Reset temp
        temp = head;
        // Store half of it in left and the other half in right
        // Create two lists and sort them
        ListNode *left = temp, *prev = NULL;
        int i = 0, mid = length / 2;
        // Left list
        while(i < mid){
            prev = temp;
            temp = temp->next;
            i++;
        }
        // The end of the left list should point to NULL
        if(prev)
            prev->next = NULL;
        // Right list
        ListNode  *right = temp;
        // Sort left list
        ListNode *sortedLeft = sortList(left);
        // Sort right list
        ListNode *sortedRight = sortList(right);
        // Merge them
        ListNode *sortedList = merge(sortedLeft, sortedRight);
        return sortedList;
    }
};

Answer 8

这是完整的代码，它展示了如何在 java 中创建链接列表并使用合并排序对其进行排序。 我正在 MergeNode 类中创建节点，还有另一个类 MergesortLinklist，其中存在划分和合并逻辑。

class MergeNode {
    Object value;
    MergeNode next;

    MergeNode(Object val) {
        value = val;
        next = null;

    }

    MergeNode() {
        value = null;
        next = null;

    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public MergeNode getNext() {
        return next;
    }

    public void setNext(MergeNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "MergeNode [value=" + value + ", next=" + next + "]";
    }

}

public class MergesortLinkList {
    MergeNode head;
    static int totalnode;

    public MergeNode getHead() {
        return head;
    }

    public void setHead(MergeNode head) {
        this.head = head;
    }

    MergeNode add(int i) {
        // TODO Auto-generated method stub
        if (head == null) {
            head = new MergeNode(i);
            // System.out.println("head value is  "+head);
            return head;

        }
        MergeNode temp = head;

        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new MergeNode(i);
        return head;

    }

    MergeNode mergesort(MergeNode nl1) {
        // TODO Auto-generated method stub

        if (nl1.next == null) {
            return nl1;
        }

        int counter = 0;

        MergeNode temp = nl1;

        while (temp != null) {
            counter++;
            temp = temp.next;

        }
        System.out.println("total nodes  " + counter);

        int middle = (counter - 1) / 2;

        temp = nl1;
        MergeNode left = nl1, right = nl1;
        int leftindex = 0, rightindex = 0;

        if (middle == leftindex) {
            right = left.next;
        }
        while (leftindex < middle) {

            leftindex++;
            left = left.next;
            right = left.next;
        }

        left.next = null;
        left = nl1;

        System.out.println(left.toString());
        System.out.println(right.toString());

        MergeNode p1 = mergesort(left);
        MergeNode p2 = mergesort(right);

        MergeNode node = merge(p1, p2);

        return node;

    }

    MergeNode merge(MergeNode p1, MergeNode p2) {
        // TODO Auto-generated method stub

        MergeNode L = p1;
        MergeNode R = p2;

        int Lcount = 0, Rcount = 0;

        MergeNode tempnode = null;

        while (L != null && R != null) {

            int val1 = (int) L.value;

            int val2 = (int) R.value;

            if (val1 > val2) {

                if (tempnode == null) {
                    tempnode = new MergeNode(val2);
                    R = R.next;
                } else {

                    MergeNode store = tempnode;

                    while (store.next != null) {
                        store = store.next;
                    }
                    store.next = new MergeNode(val2);

                    R = R.next;
                }

            } else {
                if (tempnode == null) {
                    tempnode = new MergeNode(val1);
                    L = L.next;
                } else {

                    MergeNode store = tempnode;

                    while (store.next != null) {
                        store = store.next;
                    }
                    store.next = new MergeNode(val1);

                    L = L.next;
                }

            }

        }

        MergeNode handle = tempnode;

        while (L != null) {

            while (handle.next != null) {

                handle = handle.next;

            }
            handle.next = L;

            L = null;

        }

        // Copy remaining elements of L[] if any
        while (R != null) {
            while (handle.next != null) {

                handle = handle.next;

            }
            handle.next = R;

            R = null;

        }

        System.out.println("----------------sorted value-----------");
        System.out.println(tempnode.toString());
        return tempnode;
    }

    public static void main(String[] args) {
        MergesortLinkList objsort = new MergesortLinkList();
        MergeNode n1 = objsort.add(9);
        MergeNode n2 = objsort.add(7);
        MergeNode n3 = objsort.add(6);
        MergeNode n4 = objsort.add(87);
        MergeNode n5 = objsort.add(16);
        MergeNode n6 = objsort.add(81);

        MergeNode n7 = objsort.add(21);
        MergeNode n8 = objsort.add(16);

        MergeNode n9 = objsort.add(99);
        MergeNode n10 = objsort.add(31);

        MergeNode val = objsort.mergesort(n1);

        System.out.println("===============sorted values=====================");
        while (val != null) {
            System.out.println(" value is  " + val.value);
            val = val.next;
        }
    }

}

Answer 9

最简单的 Java 实现：

时间复杂度：O(nLogn) n = 节点数。 链表的每次迭代都会使已排序的较小链表的大小加倍。 例如，在第一次迭代之后，链表将被排序为两半。 第二次迭代后，链表将被分为四半。 它将继续排序到链表的大小。 这将需要 O(logn) 倍的小链表大小才能达到原始链表大小。 nlogn中的n之所以存在，是因为链表的每次迭代所花费的时间与原始链表中的节点数成正比。

class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
    }
}

class LinkedList {
    Node head;
    public Node mergesort(Node head) {
          if(head == null || head.next == null) return head;
          Node middle = middle(head), middle_next = middle.next;
          middle.next = null;
          Node left = mergesort(head), right = mergesort(middle_next), node = merge(left, right);
          return node;
    } 

    public Node merge(Node first, Node second) {
          Node node = null;
          if (first == null) return second;
          else if (second == null) return first;
          else if (first.data <= second.data) {
              node = first;
              node.next = merge(first.next, second);

          } else {
              node = second;
              node.next = merge(first, second.next);
          }
          return node;
    }

    public Node middle(Node head) {
          if (head == null) return head;
          Node second = head, first = head.next;
          while(first != null) {
              first = first.next;
              if (first != null) {
                 second = second.next;
                 first = first.next;
              }
          }
          return second;
    }

}

Answer 10

链表非递归合并排序的另一个示例，其中函数不是类的一部分。 此示例代码和 HP / Microsoft std::list::sort 都使用相同的基本算法。 自下而上的非递归归并排序，使用指向列表第一个节点的小型（26 到 32）指针数组，其中 array[i] 为 0 或指向列表大小为 2 的 i 次方。 在我的系统 Intel 2600K 3.4ghz 上，它可以在大约 1 秒内对 400 万个节点的 32 位无符号整数作为数据进行排序。

typedef struct NODE_{
    struct NODE_ * next;
    uint32_t data;
}NODE;

NODE * MergeLists(NODE *, NODE *); /* prototype */

/* sort a list using array of pointers to list       */
/* aList[i] == NULL or ptr to list with 2^i nodes    */
 
#define NUMLISTS 32             /* number of lists */
NODE * SortList(NODE *pList)
{
NODE * aList[NUMLISTS];         /* array of lists */
NODE * pNode;
NODE * pNext;
int i;
    if(pList == NULL)           /* check for empty list */
        return NULL;
    for(i = 0; i < NUMLISTS; i++)   /* init array */
        aList[i] = NULL;
    pNode = pList;              /* merge nodes into array */
    while(pNode != NULL){
        pNext = pNode->next;
        pNode->next = NULL;
        for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){
            pNode = MergeLists(aList[i], pNode);
            aList[i] = NULL;
        }
        if(i == NUMLISTS)   /* don't go beyond end of array */
            i--;
        aList[i] = pNode;
        pNode = pNext;
    }
    pNode = NULL;           /* merge array into one list */
    for(i = 0; i < NUMLISTS; i++)
        pNode = MergeLists(aList[i], pNode);
    return pNode;
}

/* merge two already sorted lists                    */
/* compare uses pSrc2 < pSrc1 to follow the STL rule */
/*   of only using < and not <=                      */
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;          /* destination head ptr */
NODE **ppDst = &pDst;       /* ptr to head or prev->next */
    if(pSrc1 == NULL)
        return pSrc2;
    if(pSrc2 == NULL)
        return pSrc1;
    while(1){
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            if(pSrc2 == NULL){
                *ppDst = pSrc1;
                break;
            }
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            if(pSrc1 == NULL){
                *ppDst = pSrc2;
                break;
            }
        }
    }
    return pDst;
}

---

Visual Studio 2015 将 std::list::sort 更改为基于迭代器而不是列表，并且还更改为自上而下的合并排序，这需要扫描的开销。 我最初认为需要切换到自上而下才能与迭代器一起使用，但是当再次询问时，我对此进行了调查并确定不需要切换到较慢的自上而下方法，并且可以使用自下而上来实现相同的基于迭代器的逻辑。 此链接中的答案解释了这一点，并提供了一个独立的示例以及包含文件“list”中 VS2019 的 std::list::sort() 的替代品。

`std::list<>:: sort()` - 为什么突然切换到自上而下的策略？

Answer 11

一个经过测试、有效的 C++ 版本的单链表，基于得票最高的答案。

singlelinkedlist.h：

#pragma once
#include <stdexcept>
#include <iostream>
#include <initializer_list>
namespace ythlearn{
    template<typename T>
    class Linkedlist{
    public:
        class Node{
        public:
            Node* next;
            T elem;
        };
        Node head;
        int _size;
    public:
        Linkedlist(){
            head.next = nullptr;            
            _size = 0;
        }

        Linkedlist(std::initializer_list<T> init_list){
            head.next = nullptr;            
            _size = 0;
            for(auto s = init_list.begin(); s!=init_list.end(); s++){
                push_left(*s);
            }
        }

        int size(){
            return _size;
        }

        bool isEmpty(){
            return size() == 0;
        }

        bool isSorted(){
            Node* n_ptr = head.next;
            while(n_ptr->next != nullptr){
                if(n_ptr->elem > n_ptr->next->elem)
                    return false;
                n_ptr = n_ptr->next;
            }
            return true;
        }

        Linkedlist& push_left(T elem){
            Node* n = new Node;
            n->elem = elem;
            n->next = head.next;
            head.next = n;
            ++_size;
            return *this;
        }

        void print(){
                Node* loopPtr = head.next;
                while(loopPtr != nullptr){
                    std::cout << loopPtr->elem << " ";
                    loopPtr = loopPtr->next;
                }
                std::cout << std::endl;
        }

        void call_merge(){
            head.next = merge_sort(head.next);
        }

        Node* merge_sort(Node* n){
            if(n == nullptr || n->next == nullptr)
                return n;
            Node* middle = getMiddle(n);
            Node* left_head = n;
            Node* right_head = middle->next;
            middle->next = nullptr;
            return merge(merge_sort(left_head), merge_sort(right_head));
        }

        Node* getMiddle(Node* n){
            if(n == nullptr)
                return n;
            Node* slow, *fast;
            slow = fast = n;
            while(fast->next != nullptr && fast->next->next != nullptr){
                slow = slow->next;
                fast = fast->next->next;
            }
            return slow;
        }

        Node* merge(Node* a, Node* b){
            Node dummyHead;
            Node* current = &dummyHead;
            while(a != nullptr && b != nullptr){
                if(a->elem < b->elem){
                    current->next = a;
                    a = a->next;
                }else{
                    current->next = b;
                    b = b->next;
                }
                current = current->next;
            }
            current->next = (a == nullptr) ? b : a;
            return dummyHead.next;
        }

        Linkedlist(const Linkedlist&) = delete;
        Linkedlist& operator=(const Linkedlist&) const = delete;
        ~Linkedlist(){
            Node* node_to_delete;
            Node* ptr = head.next;
            while(ptr != nullptr){
                node_to_delete = ptr;
                ptr = ptr->next;
                delete node_to_delete;
            }

        }

    };
}

ma​​in.cpp：

#include <iostream>
#include <cassert>
#include "singlelinkedlist.h"
using namespace std;
using namespace ythlearn;

int main(){
    Linkedlist<int> l = {3,6,-5,222,495,-129,0};
    l.print();
    l.call_merge();
    l.print();
    assert(l.isSorted());
    return 0;
}

Answer 12

mono eglib< 中有一个非递归链表合并排序/a>.

基本思想是各种合并的控制循环与二进制整数的按位增量并行。 有 O(n) 次合并将 n 个节点“插入”到合并树中，这些合并的排名对应于递增的二进制数字。 使用此类比，只需将合并树的 O(log n) 个节点具体化为临时保存数组。

Answer 13

这是我对 Knuth 的“列表合并排序”的实现（来自 TAOCP 第 3 卷第 2 版的算法 5.2.4L）。 我将在最后添加一些注释，但这里有一个摘要：

在随机输入上，它的运行速度比 Simon Tatham 的代码快一点（请参阅 Dave Gamble 的非递归答案，带有链接），但比 Dave Gamble 的递归代码慢一点。 它比任何一个都更难理解。 至少在我的实现中，它要求每个元素有两个指向元素的指针。 （另一种选择是一个指针和一个布尔标志。）因此，这可能不是一种有用的方法。 然而，一个显着的一点是，如果输入具有已经排序的长段，则它运行得非常快。

element *knuthsort(element *list)
{ /* This is my attempt at implementing Knuth's Algorithm 5.2.4L "List merge sort"
     from Vol.3 of TAOCP, 2nd ed. */
  element *p, *pnext, *q, *qnext, head1, head2, *s, *t;
  if(!list) return NULL;

L1: /* This is the clever L1 from exercise 12, p.167, solution p.647. */
  head1.next=list;
  t=&head2;
  for(p=list, pnext=p->next; pnext; p=pnext, pnext=p->next) {
    if( cmp(p,pnext) > 0 ) { t->next=NULL; t->spare=pnext; t=p; }
  }
  t->next=NULL; t->spare=NULL; p->spare=NULL;
  head2.next=head2.spare;

L2: /* begin a new pass: */
  t=&head2;
  q=t->next;
  if(!q) return head1.next;
  s=&head1;
  p=s->next;

L3: /* compare: */
  if( cmp(p,q) > 0 ) goto L6;
L4: /* add p onto the current end, s: */
  if(s->next) s->next=p; else s->spare=p;
  s=p;
  if(p->next) { p=p->next; goto L3; } 
  else p=p->spare;
L5: /* complete the sublist by adding q and all its successors: */
  s->next=q; s=t;
  for(qnext=q->next; qnext; q=qnext, qnext=q->next);
  t=q; q=q->spare;
  goto L8;
L6: /* add q onto the current end, s: */
  if(s->next) s->next=q; else s->spare=q;
  s=q;
  if(q->next) { q=q->next; goto L3; } 
  else q=q->spare;
L7: /* complete the sublist by adding p and all its successors: */
  s->next=p;
  s=t;
  for(pnext=p->next; pnext; p=pnext, pnext=p->next);
  t=p; p=p->spare;
L8: /* is this end of the pass? */
  if(q) goto L3;
  if(s->next) s->next=p; else s->spare=p;
  t->next=NULL; t->spare=NULL;
  goto L2;
}

Answer 14

我决定测试这里的示例，以及另一种方法，最初由 Jonathan Cunningham 在 Pop-11 中编写。 我用 C# 编写了所有方法，并与一系列不同的列表大小进行了比较。 我比较了 Raja R Harinath 的 Mono eglib 方法、Shital Shah 的 C# 代码、Jayadev 的 Java 方法、David Gamble 的递归和非递归版本、Ed Wynn 的第一个 C 代码（这与我的示例数据集崩溃了，我没有调试）和坎宁安的版本。 完整代码位于：https://gist.github.com/314e572808f29adb0e41.git。

Mono eglib 基于与 Cunningham 类似的想法，并且速度相当，除非列表恰好已经排序，在这种情况下 Cunningham 的方法要快得多（如果部分排序，eglib 会稍微快一些）。 eglib 代码使用固定表来保存合并排序递归，而 Cunningham 的方法通过使用递增级别的递归来工作 - 因此它开始使用无递归，然后是 1 深度递归，然后是 2 深度递归，依此类推，根据需要多少步来进行排序。 我发现坎宁安代码更容易理解，并且无需猜测递归表的大小，因此它得到了我的投票。 我在此页面尝试的其他方法速度慢两倍或更多倍。

下面是 Pop-11 排序的 C# 端口：

/// <summary>
/// Sort a linked list in place. Returns the sorted list.
/// Originally by Jonathan Cunningham in Pop-11, May 1981.
/// Ported to C# by Jon Meyer.
/// </summary>
public class ListSorter<T> where T : IComparable<T> {
    SingleListNode<T> workNode = new SingleListNode<T>(default(T));
    SingleListNode<T> list;

    /// <summary>
    /// Sorts a linked list. Returns the sorted list.
    /// </summary>
    public SingleListNode<T> Sort(SingleListNode<T> head) {
        if (head == null) throw new NullReferenceException("head");
        list = head;

        var run = GetRun(); // get first run
        // As we progress, we increase the recursion depth. 
        var n = 1;
        while (list != null) {
            var run2 = GetSequence(n);
            run = Merge(run, run2);
            n++;
        }
        return run;
    }

    // Get the longest run of ordered elements from list.
    // The run is returned, and list is updated to point to the
    // first out-of-order element.
    SingleListNode<T> GetRun() {
        var run = list; // the return result is the original list
        var prevNode = list;
        var prevItem = list.Value;

        list = list.Next; // advance to the next item
        while (list != null) {
            var comp = prevItem.CompareTo(list.Value);
            if (comp > 0) {
                // reached end of sequence
                prevNode.Next = null;
                break;
            }
            prevItem = list.Value;
            prevNode = list;
            list = list.Next;
        }
        return run;
    }

    // Generates a sequence of Merge and GetRun() operations.
    // If n is 1, returns GetRun()
    // If n is 2, returns Merge(GetRun(), GetRun())
    // If n is 3, returns Merge(Merge(GetRun(), GetRun()),
    //                          Merge(GetRun(), GetRun()))
    // and so on.
    SingleListNode<T> GetSequence(int n) {
        if (n < 2) {
            return GetRun();
        } else {
            n--;
            var run1 = GetSequence(n);
            if (list == null) return run1;
            var run2 = GetSequence(n);
            return Merge(run1, run2);
        }
    }

    // Given two ordered lists this returns a list that is the
    // result of merging the two lists in-place (modifying the pairs
    // in list1 and list2).
    SingleListNode<T> Merge(SingleListNode<T> list1, SingleListNode<T> list2) {
        // we reuse a single work node to hold the result.
        // Simplifies the number of test cases in the code below.
        var prevNode = workNode;
        while (true) {
            if (list1.Value.CompareTo(list2.Value) <= 0) {
                // list1 goes first
                prevNode.Next = list1;
                prevNode = list1;
                if ((list1 = list1.Next) == null) {
                    // reached end of list1 - join list2 to prevNode
                    prevNode.Next = list2;
                    break;
                }
            } else {        // same but for list2
                prevNode.Next = list2;
                prevNode = list2;
                if ((list2 = list2.Next) == null) {
                    prevNode.Next = list1;
                    break;
                }
            }
        }

        // the result is in the back of the workNode
        return workNode.Next;
    }
}

Answer 15

我一直痴迷于优化该算法的混乱，下面是我最终得到的结果。 互联网和 StackOverflow 上的许多其他代码都非常糟糕。 有人试图获得列表的中间点，进行递归，对剩余节点进行多个循环，维护大量事物的计数 - 所有这些都是不必要的。 归并排序自然适合链表，算法可以很漂亮且紧凑，但要达到这种状态并不容易。

据我所知，下面的代码维护了最少数量的变量，并且具有算法所需的最少逻辑步骤（即不会使代码不可维护/不可读）。 然而，我并没有尝试最小化 LOC 并保留尽可能多的空白以保持可读性。 我已经通过相当严格的单元测试测试了这段代码。

请注意，此答案结合了其他答案https://stackoverflow.com/a/3032462/207661中的一些技术。 虽然代码是用 C# 编写的，但转换为 C++、Java 等应该很简单。

SingleListNode<T> SortLinkedList<T>(SingleListNode<T> head) where T : IComparable<T>
{
    int blockSize = 1, blockCount;
    do
    {
        //Maintain two lists pointing to two blocks, left and right
        SingleListNode<T> left = head, right = head, tail = null;
        head = null; //Start a new list
        blockCount = 0;

        //Walk through entire list in blocks of size blockCount
        while (left != null)
        {
            blockCount++;

            //Advance right to start of next block, measure size of left list while doing so
            int leftSize = 0, rightSize = blockSize;
            for (;leftSize < blockSize && right != null; ++leftSize)
                right = right.Next;

            //Merge two list until their individual ends
            bool leftEmpty = leftSize == 0, rightEmpty = rightSize == 0 || right == null;
            while (!leftEmpty || !rightEmpty)
            {
                SingleListNode<T> smaller;
                //Using <= instead of < gives us sort stability
                if (rightEmpty || (!leftEmpty && left.Value.CompareTo(right.Value) <= 0))
                {
                    smaller = left; left = left.Next; --leftSize;
                    leftEmpty = leftSize == 0;
                }
                else
                {
                    smaller = right; right = right.Next; --rightSize;
                    rightEmpty = rightSize == 0 || right == null;
                }

                //Update new list
                if (tail != null)
                    tail.Next = smaller;
                else
                    head = smaller;
                tail = smaller;
            }

            //right now points to next block for left
            left = right;
        }

        //terminate new list, take care of case when input list is null
        if (tail != null)
            tail.Next = null;

        //Lg n iterations
        blockSize <<= 1;

    } while (blockCount > 1);

    return head;
}

兴趣点

• 对于 1 列表的空列表等情况，不需要进行特殊处理。 这些案例“确实有效”。
• 许多“标准”算法文本都有两个循环来遍历剩余元素，以处理一个列表比另一个列表短的情况。 上面的代码消除了对它的需要。
• 我们确保排序是稳定的
• 内部 while 循环是一个热点，平均每次迭代计算 3 个表达式，我认为这是最少的。

更新：@ideasman42 将上述代码翻译为 C/C++ 以及修复注释和位的建议更多改进。 上面的代码现在已与这些代码保持同步。

Answer 16

这是一个替代的递归版本。 这不需要沿着列表进行分割：我们提供一个指向头元素（不是排序的一部分）的指针和一个长度，并且递归函数返回一个指向已排序列表末尾的指针。

element* mergesort(element *head,long lengtho)
{ 
  long count1=(lengtho/2), count2=(lengtho-count1);
  element *next1,*next2,*tail1,*tail2,*tail;
  if (lengtho<=1) return head->next;  /* Trivial case. */

  tail1 = mergesort(head,count1);
  tail2 = mergesort(tail1,count2);
  tail=head;
  next1 = head->next;
  next2 = tail1->next;
  tail1->next = tail2->next; /* in case this ends up as the tail */
  while (1) {
    if(cmp(next1,next2)<=0) {
      tail->next=next1; tail=next1;
      if(--count1==0) { tail->next=next2; return tail2; }
      next1=next1->next;
    } else {
      tail->next=next2; tail=next2;
      if(--count2==0) { tail->next=next1; return tail1; }
      next2=next2->next;
    }
  }
}

Answer 17

一种有趣的方法是维护一个堆栈，只有当堆栈上的列表具有相同数量的元素时才合并，否则推送列表，直到用完传入列表中的元素，然后向上合并堆栈。

Answer 18

最简单的是来自
Gonnet + Baeza Yates 算法手册。 您可以使用所需的排序元素数量来调用它，该元素会递归地一分为二，直到达到对大小为一的列表的请求，然后您只需将原始列表的前面剥离即可。 这些都被合并到一个完整大小的排序列表中。

[请注意，第一篇文章中基于堆栈的很酷的排序称为在线合并排序，它在 Knuth 第 3 卷的练习中被提及得最少]

Answer 19

想知道为什么它应该是一个巨大的挑战，正如这里所述，这里是一个简单的 Java 实现，没有任何“聪明的技巧”。

//The main function
public static Node merge_sort(Node head) 
{
    if(head == null || head.next == null) 
        return head;
        
    Node middle = getMiddle(head);      //get the middle of the list
    Node left_head = head;
    Node right_head = middle.next; 
    middle.next = null;             //split the list into two halfs

    return merge(merge_sort(left_head), merge_sort(right_head));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public static Node merge(Node a, Node b)
{
    Node dummyHead = new Node();
    for(Node current  = dummyHead; a != null && b != null; current = current.next;)
    {
        if(a.data <= b.data) 
        {
            current.next = a; 
            a = a.next; 
        }
        else
        { 
            current.next = b;
            b = b.next; 
        }
        
    }
    dummyHead.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public static Node getMiddle(Node head)
{
    if(head == null) 
        return head;
    
    Node slow = head, fast = head;
    
    while(fast.next != null && fast.next.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Answer 20

更简单/更清晰的实现可能是递归实现，从中 NLog(N) 执行时间更清晰。

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
    // some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
    // Trivial case.
    if (!list || !list->next)
        return list;

    aList *right = list,
          *temp  = list,
          *last  = list,
          *result = 0,
          *next   = 0,
          *tail   = 0;

    // Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next)
    {
        last = right;
        right = right->next;
        temp = temp->next->next;
    }

    // Break the list in two. (prev pointers are broken here, but we fix later)
    last->next = 0;

    // Recurse on the two smaller lists:
    list = merge_sort_list_recursive(list, compare);
    right = merge_sort_list_recursive(right, compare);

    // Merge:
    while (list || right)
    {
        // Take from empty lists, or compare:
        if (!right) {
            next = list;
            list = list->next;
        } else if (!list) {
            next = right;
            right = right->next;
        } else if (compare(list, right) < 0) {
            next = list;
            list = list->next;
        } else {
            next = right;
            right = right->next;
        }
        if (!result) {
            result=next;
        } else {
            tail->next=next;
        }
        next->prev = tail;  // Optional.
        tail = next;
    }
    return result;
}

注意：这对递归有 Log(N) 存储要求。 性能应该与我发布的其他策略大致相当。 这里有一个潜在的优化，通过运行合并循环 while (list && right)，并简单地附加剩余的列表（因为我们并不真正关心列表的末尾；知道它们被合并就足够了） 。