由于链表（LinkedList）不支持随机访问（Random Access），只允许顺序访问，因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法，而归并排序可以满足这一需求。

归并排序是分治法（Divide and Conquer）的典型应用，其伪代码如下：

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

下面的Java代码实现了对单链表（singly linked list）的归并排序，代码实现优美，可读性强，具有较高的参考价值：

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

    return merge(merge_sort(head), merge_sort(sHalf)); // recurse on that
}

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

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

链表节点Node的定义如下：

public class Node {
    public Node next;
    public int val;
}

原文链接：http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list/

本文链接：http://bookshadow.com/weblog/2014/11/21/java-merge-sort-of-linked-list/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码