在诸多排序算法中，归并排序（merge sort）无疑是我印象最为深刻的一种，这要源于在某位学长讲解算法让我尝试实现归并排序时，我卡在寻找中点的那一步毫无头绪时，得知还有快慢指针这种神器的震撼（谁能想到我是从归并排序接触到双指针的，天

归并排序是使用分治的思想，把待排序的集合分段直至不可再分，当集合中只有一个元素的时候，这个集合就自然成为了一个已排序好的集合，此时，我们在将其合并即可。

归并排序的时间复杂度是$O(n\log{n})$，空间复杂度是$O(n)$。

算法实现

数组的实现

在数组中分治是比较简单的，困难的一点主要在合并上。因为数组的内存是连续的，我们没法从中间开辟出一块内存，必须找一块新的内存存放。

//分治
void mergeSort(std::vector<int>& nums,int left,int right,std::vector<int>& temp){
    if(left>=right){
        return ;
    }
    int mid=left+(right-left)/2;
    
    mergeSort(nums,left,mid,temp);
    mergeSort(nums,mid+1,right,temp);
    
    merge(nums,left,mid,right,temp);
}

//合并
void merge(std::vector<int>& nums,int left,int mid,int right,std::vectoe<int>& temp){
    int i=left;
    int j=mid+1;
    int k=left;
    
    while(i<=mid && j<=right){
        if(nums[i]<=nums[j]){
            temp{k++}=nums[i++];
        }else{
            temo[k++]=nums[j++];
        }
        
    }
    while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 如果右半边还有剩下的，全部打包带走
        while (j <= right) {
            temp[k++] = nums[j++];
        }

        // 恢复原数组内容
        for (int p = left; p <= right; p++) {
            nums[p] = temp[p];
        }
}

链表的实现

链表在实现归并排序的时候最困难的一步是分治中的如何取到中点，所以我们在这里考虑使用快慢指针来解决这个问题。

什么是快慢指针？假设这里有一个链表1->2->3->4，我们现在给出两个指针，让慢指针slow指向1，快指针fast指向2，接着进行迭代，让快慢指针同时移动，快指针每次比慢指针多移动一步——当快指针移动到最后一个节点的时候，慢指针刚好移动到了中点！

好了，我们已经实现了找到中点，然后分成两端，在把他们分别丢给递归小盒，Done！

最后合并他们就完成了全部的归并排序了。

拿 LeetCode 的 148.排序链表 来举个例子

148. 排序链表 中等

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 104] 内
• -105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr || head->next==nullptr){
            return head;
        }

        ListNode* fast=head->next; //快指针指向第二个节点
        ListNode* slow=head; //慢指针指向第一个节点

        while(fast!=nullptr && fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
            // 快指针每次都比慢指针多走一步
        }
        ListNode* mid=slow->next; //当快指针走到终点时，慢指针所在的位置刚好就是中点
        slow->next=nullptr; //切断前后两半的链表
        //递归分治所有的节点
        ListNode* left=sortList(head);
        ListNode* right=sortList(mid);
        //调用合并函数合并
        return merge(left,right);
    }

private:
    ListNode* merge(ListNode* list1,ListNode* list2){
        ListNode dummy(-1); //创建一个虚拟头节点
        ListNode* curr=&dummy; //将dummy的引用赋值给curr

        while(list1!=nullptr && list2!=nullptr){
            if(list1->val < list2->val){
                // list1小的情况
                curr->next=list1; //给list1的节点挂到curr后面
                list1=list1->next; //步进
            }else{
                //list2小的情况
                curr->next=list2; //给list2的节点挂到curr后面
                list2=list2->next; //步进
            }
            curr=curr->next; //步进
        }
        curr->next=(list1!=nullptr)?list1:list2; //list1 里面还有剩下的节点吗？如果有，挂list1，否则挂list2
        return dummy.next;
    }
};

这份代码用自顶向下的递归归并排序实现了$O(n\log{n})$的时间复杂度和$O(\log{N})$的空间复杂度。

但是题目对我们提出了更高的要求，做到$O(1)$的空间复杂度。

这时候我们就要使用自底向上的迭代归并排序。

先遍历得到链表的长度，然后将链表拆成长度为1的子链表，他们本身已经排序好，两两合并；现在每个有序子链表的长度变成了2，再进行两两合并，每个有序子链表的长度就变成了4，……，以此类推，最后就可以得到排序好的链表。

但是在实现时需要多写一个split函数，较为复杂，下面是CPP的实现代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr) return nullptr;

        // 遍历得到链表长度
        int length = 0;
        ListNode* node = head;
        while (node != nullptr) {
            length++;
            node = node->next;
        }

        // 哨兵节点
        ListNode dummy(-1, head);

        // 外层循环：控制步长 step，每次翻倍 (1, 2, 4, 8...)
        for (int step = 1; step < length; step *= 2) {
            // prev 永远站在“已经合并好的部分”的尾巴上，负责把新合并的片段缝上去
            ListNode* prev = &dummy;
            // curr 是我们的探路兵，负责在前面切香肠
            ListNode* curr = dummy.next;

            // 内层循环：按当前 step 大小，一路往下切分并合并
            while (curr != nullptr) {
                // 第一刀：切出长度为 step 的 list1
                ListNode* head1 = curr;
                ListNode* head2 = split(head1, step);

                // 第二刀：切出长度为 step 的 list2
                // split 会把切完 list2 后剩下的链表头部返回给 curr，准备下一对的循环
                curr = split(head2, step); 

                // 把切下来的 list1 和 list2 合并
                ListNode* mergedHead = merge(head1, head2);

                // 缝合：把 prev 的尾巴连上刚刚合并好的新片段
                prev->next = mergedHead;

                // 把 prev 往前挪，挪到刚刚缝上去的这个新片段的最后面，准备接下一段
                while (prev->next != nullptr) {
                    prev = prev->next;
                }
            }
        }
        return dummy.next;
    }

private:
    // 切割链表
    // 从 head 开始切掉 n 个节点，切断联系，并返回剩下的链表头部
    ListNode* split(ListNode* head, int n) {
        if (head == nullptr) return nullptr;
        
        // 往前走 n-1 步，停在要切断的那个节点上
        // 注意：如果链表长度不够 n 了，走到尽头也要停下
        for (int i = 1; i < n && head->next != nullptr; i++) {
            head = head->next;
        }
        
        ListNode* nextChunk = head->next; // 存储剩余节点
        head->next = nullptr;             // 剪断
        return nextChunk;                 // 返回剩余节点
    }

    // 合并链表
    ListNode* merge(ListNode* list1, ListNode* list2) {
        ListNode dummy(-1);
        ListNode* curr = &dummy;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        curr->next = (list1 != nullptr) ? list1 : list2;
        return dummy.next;
    }
};