chapter_sorting/merge_sort/

[giscus[bot]]

chapter_sorting/merge_sort/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_sorting/merge_sort/

[zxc1518343069]

你好，想请问一下上述图片是通过什么制作的

[krahets]

哈喽，用 Keynote 哈

[zxc1518343069]

您好，您写的非常棒。还想请问一下有后续迭代的计划吗？ 比如 补充 十大排序中其他的?

[krahets]

@zxc1518343069 感谢鼓励！有的，正在加紧更新中～ 其他排序算法会在将来更新哒

[SMNrootQYS]

写的很棒

[krahets]

谢谢鼓励！

[iron-irax]

感谢大佬，对于菜鸟如我来说真是相见恨晚又恨早。期待后续更新！

[krahets]

谢谢鼓励～会加油更新的！！

[gltianwen]

    public static int[] mergeSorting(int[] nums){
        if (nums.length <= 1) {
            return nums;
        }
        int num = nums.length >> 1;
        int[] left = Arrays.copyOfRange(nums, 0, num);
        int[] right = Arrays.copyOfRange(nums, num, nums.length);
        return merge(mergeSorting(left), mergeSorting(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[left.length + right.length];

        while(i < left.length && j < right.length){
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
        
        return result;
    }

这样会不会更简洁

[krahets]

So clean!

[yy1781051483]

今年实习机考，就是一个归并排序相见恨晚

[yy1781051483]

不会是华为5月份那一批吧，我也是

[krahets]

不会是华为5月份那一批吧，我也是

震惊！我竟回复我自己（doge）

[mao888]

你好，将merge函数里的for循环，里的第三个else合并到第一个 if 里面可以吗，他俩的逻辑和第二个if一样的呀。我尝试之后，panic: runtime error: index out of range [2] with length 2 。
能帮我解答一下吗？
是否能把第三个else合并到第一个，能，麻烦出一下代码，不能的话，恳请指导一下原因。

 // 通过覆盖原数组 nums 来合并左子数组和右子数组
	for k := left; k <= right; k++ {
		// 若“左子数组已全部合并完”或“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
		if i > leftEnd || tmp[i] > tmp[j] {
			nums[k] = tmp[j]
			j++
			// 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++
		} else if j > rightEnd || tmp[i] <= tmp[j] {
			nums[k] = tmp[i]
			i++
			// 否则，若“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
		}
		//else {
		//	nums[k] = tmp[j]
		//	j++
		//}
	}

[krahets]

哈喽，两种写法不是等价的。把条件 3 合并到条件 1 后，当出现 tmp[i] > tmp[j] 时就会直接执行条件 1 ，但是此时可能右子数组已经合并完了（即条件 2 中的 j > rightEnd），这样就出现了越界报错。

[mao888]

感谢，希望佬继续更新后续的排序算法!

[DoubtedYapper71]

问一下后续有动态规划的计划吗？

[krahets]

哈喽～有的，不过比较靠后

[JocyeI]

最近几天看了很2~3遍，收益匪浅！感想遇见！还望K神开通捐赠通道。

[krahets]

哇 这几天看到的最暖心的评论！谢谢鼓励，捐赠还是算了吧哈哈哈，毕竟是免费的

[zwrong]

清晰的，通过看图一下子明白原理是怎么样的。先看一遍K神的算法图，快速回忆一下算法，然后上课听老师讲效率高

[zwrong]

K神，能够把归并的过程也画个图呢？感觉可以更直观的看出是怎么归并，方便与快速排序比较。
我先自己尝试画一下

[krahets]

HI! 归并排序有图呀，你是说想要更详细的图吗？

[zwrong]

看到了看到了，应该是我浏览器的原因没有显示，不好意思。
图画的很棒，一看就懂

[lethexixin]

链表排序：具体实现细节比较复杂，有兴趣的同学可以查阅相关资料进行学习

[lethexixin]

K神，这个链表排序，有没有比较好的参考链接推荐的呀

[krahets]

Hi, 我以前写过一个相关题解 148. 排序链表

[TDB001]

1 if (i > leftEnd)
2 nums[k] = tmp[j++];
3 // 否则，若“右子数组已全部合并完”或“左子数组元素 <= 右子数组元素”，则选取左子数组元素，并且 i++
4 else if (j > rightEnd || tmp[i] <= tmp[j])
5 nums[k] = tmp[i++];
6 // 否则，若“左右子数组都未全部合并完”且“左子数组元素 > 右子数组元素”，则选取右子数组元素，并且 j++
7 else
8 nums[k] = tmp[j++];

k神第1、2行是否冗余了，删除即可？

[krahets]

Hi 不是冗余的哈，如果去掉了，当 i > leftEnd 成立的时候，也可能进入第 4 行的分支。可以删掉运行下代码看看

[TDB001]

好的，谢谢

[zhgqcn]

K神好，我刷Leetcode 剑指 Offer 51. 数组中的逆序对，用了上述代码，会有部分用例问题，但是不知道错在哪，能否请教下

class Solution {
    int res = 0;
    public int reversePairs(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        mergeSort(nums, left, right);
        return res;
    }

    public void mergeSort(int[] nums, int left, int right){
        if(left >= right){
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    public void merge(int[] nums, int left, int mid, int right){
        int[] tmp = Arrays.copyOfRange(nums, left, right + 1);
        int leftStart = left - left, leftEnd = mid - left;
        int rightStart = mid + 1 - left, rightEnd = right - left;
        int i = leftStart, j = rightStart;
        for(int k = left; k <= right; k++){
            if(i > leftEnd){
                nums[k] = tmp[j++];
            }else if(j > rightEnd || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                System.out.println(mid - i + 1);
                res += mid - i + 1;
                nums[k] = tmp[j++];
            }
        }
    }
}

[zhgqcn]

问题解决

res += mid - left - i + 1;

• 有点隐蔽

[zhuasdfg]

这也太难了吧，那个merge()中的比较 tmp[i] 和 tmp[j] 的大小和i，j的各种操作，我看了好久，画图推了半天才看明白原理，但也就最多做到勉强看懂这么写能得到结果，这代码我只能感叹把指针玩出花来了，泰裤辣！

[krahets]

更新了一版新的实现，现在应该简单一些啦～

[Boiling-water]

k神可以出一篇迭代和递归的算法。其他算法里总是提到这两个算法，看的多了，发现越看越迷糊

[krahets]

确实！

[Boiling-water]

期待哈

[TDB001]

func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
// 初始化辅助数组
let tmp = Array(nums[left ..< (right + 1)])

[TDB001]

k神，swift这一行写成闭区间就可以把，可以少个加法运算 let tmp = Array(nums[left...right])

[krahets]

只要两个区间是等价的就行～

[Heyuan520]

这个是链表形式的归并代码

class ListNode:
    def __init__(self, val: int = 0):
        self.val = val
        self.next = None


class Solution:
    def mergeSort(self, head: ListNode) -> ListNode:
        if head or head.next:
            return head
        mid = self.getMiddle(head)
        left = head
        right = mid.next
        mid.next = None

        self.mergeSort(left)
        self.mergeSort(right)

        return self.merge(left, right)

    def getMiddle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def merge(self, left: ListNode, right: ListNode) -> ListNode:
        damn = ListNode()
        temp = damn

        while left and right:
            if left.val <= right.val:
                temp.next = left
                left = left.next
            else:
                temp.next = right
                right = right.next

        temp.next = left if left else right
        return damn.next

[a943862842]

mergeSort函数的递归出口是不是应该是只有一个节点的时候，所以应该是“head and not head.next”呢

[Coolllh]

这是链表的归并Java实现代码，使用了递归，过会发一个不适用递归的，题目可见LeetCode 148

//此法为归并排序自顶向下 空间复杂度O(logn)    
public ListNode sortList(ListNode head) {
    return sortList(head, null);
}


public ListNode sortList(ListNode head, ListNode tail) {
    if (head == null) {
        return null;
    }
    if (head.next == tail) {
        head.next = null;
        return head;
    }
    // 快慢指针，将链表分成两部分
    ListNode slow = head;
    ListNode fast = head;
    while (fast != tail) {
        slow = slow.next;
        fast = fast.next;
        if (fast != tail) {
            fast = fast.next;
        }
    }
    ListNode list1 = sortList(head, slow);
    ListNode list2 = sortList(slow, fast);
    return merge(list1, list2);
}

public ListNode merge(ListNode node1, ListNode node2) {
    ListNode returnNode = new ListNode(0);
    ListNode temp = returnNode;
    while (node1 != null && node2 != null) {
        if (node1.val <= node2.val) {
            temp.next = node1;
            node1 = node1.next;
        } else {
            temp.next = node2;
            node2 = node2.next;
        }
        temp = temp.next;
    }

    temp.next = node1 == null ? node2 : node1;

    return returnNode.next;
}

[Coolllh]

这是不使用递归的归并排序

public ListNode sortList(ListNode head) {
    if (head == null) {
        return null;
    }
    int length = 0;
    ListNode node = head;
    while (node != null) {
        length++;
        node = node.next;
    }
    ListNode newHead = new ListNode(0, head);
    for (int subLength = 1; subLength < length; subLength <<= 1) {
        ListNode pre = newHead;
        ListNode currentNode = pre.next;
        while (currentNode != null) {

            ListNode list1 = currentNode;
            for (int i = 1; i < subLength && currentNode.next != null; i++) {
                currentNode = currentNode.next;
            }
            ListNode list2 = currentNode.next;
            currentNode.next = null;
            currentNode = list2;
            for (int i = 1; i < subLength && currentNode != null && currentNode.next != null; i++) {
                currentNode = currentNode.next;
            }
            ListNode next = null;
            if (currentNode != null) {
                next = currentNode.next;
                currentNode.next = null;
            }
            pre.next= merge(list1, list2);
           while(pre.next!=null){
               pre=pre.next;
           }
           currentNode=next;
        }

    }
    return newHead.next;
}
public ListNode merge(ListNode node1, ListNode node2) {
    ListNode returnNode = new ListNode(0);
    ListNode temp = returnNode;
    while (node1 != null && node2 != null) {
        if (node1.val <= node2.val) {
            temp.next = node1;
            node1 = node1.next;
        } else {
            temp.next = node2;
            node2 = node2.next;
        }
        temp = temp.next;
    }

    temp.next = node1 == null ? node2 : node1;

    return returnNode.next;
}

[tstanon]

归并排序的递归和非递归实现C语言代码

// 归并排序
void merge(float *x, int sl, int sr){
    float *l_start = x, *r_start = x + sl, *tmp = (float *)malloc((sl + sr) * sizeof(float)); int i = 0, j = 0, k = 0;
    while (i < sl && j < sr){ if (l_start[i] <= r_start[j]) { tmp[k++] = l_start[i++]; } else { tmp[k++] = r_start[j++]; } }
    while (i < sl) { tmp[k++] = l_start[i++]; } while (j < sr) { tmp[k++] = r_start[j++]; }
    for (i = 0; i < sl + sr; i++) { x[i] = tmp[i]; } free(tmp);
}
void merge_sort_rec(float *x, int size){ if (size > 1){ int sl = size / 2, sr = size - sl; merge_sort_rec(x, sl); merge_sort_rec(x + sl, sr); merge(x, sl, sr); } }
void merge_sort_nrec(float *x, int size) {
    for (int width = 1; width < size; width *= 2) { // width of each part : 1, 2, 4, 8, ...; e.g. 1 + 1 -> 2; 2 + 2 -> 4; 4 + 4 -> 8; ...
        int left = 0;
        while (left < size) { // 合并每一对子数组
            int mid = left + width - 1, right = (mid + width < size) ? mid + width : size - 1;  // [left, mid], [mid+1, right] ; 此处限制了right的范围，避免超出数组的大小
            if (mid < size - 1) {  merge(x + left, mid - left + 1, right - mid); }// 当前子数组确实有需要合并的右侧部分，才进行合并操作。
            left += 2 * width;
        }
    }
}

[Wangbuwang]

新入门菜鸡，我想问问上面的递归中归并排序空间复杂度不是O(nlogn),为什么写的时O(n),求
大神赐教

[tstanon]

都是O(nlogn)吧，您是什么地方看到O(n)复杂度的呢？
就拿非递归举例，合并的宽度从1, 2, 4, 8, 到width，复杂度是log_2(n)。每次合并遍历全部的数组长度，即：O(n)。相乘就是O(nlogn)。
以递归举例，一开始分为2份，之后是4，8, ...，一直到n份。所以划分的次数是log_2(n)，划分之后需要做递归归并，归并两侧，合起来长度就是整个数组长度，因此是O(n)，相乘是O(nlogn)。

[ruihao-yan]

请问，是不是递阶段时间复杂度为O(1)，归阶段时间复杂度为O(N)呢？因为要合并连个有序数组

[tstanon]

噢噢，不好意思，我看成时间复杂度了。空间复杂度是 o(n)的，这个跟递归啥关系不大。主要看 merge 这个函数，开辟了新空间用于存有序数组，即两个子序列排序结果。排序整个数组所需新空间刚好就是数组长度 n。

[Akane0238]

我的理解是每层递归的栈帧空间O(logn)+每层使用O(N)的额外数组，而因为每层递归结束就会释放额外数组的栈内存，所以总的空间复杂度是O(n+logn)

[1595690293]

K神，我不太习惯针对原数组进行操作，我习惯进行一个返回指，写成下面这样。如果写成下面这样，请问空间复杂度是不是会增加？

[1595690293]

def merge(left_list:list[int], right_list:list[int]) -> list[int]:
    i, j = 0, 0
    len_left, len_right = len(left_list), len(right_list)
    merge_list = []
    while i<len_left and j<len_right: # 注意边界条件
        if left_list[i] > right_list[j]:
            merge_list.append(right_list[j])
            j += 1
        else:
            merge_list.append(left_list[i])
            i += 1
    # 左边有剩余元素
    if i<len_left and j>=len_right:
        merge_list += left_list[i:len_left+1]
    # 右边有剩余元素
    if i>=len_left and j<len_right:
        merge_list += right_list[j:len_right + 1]
    return merge_list

def merge_sort(nums:list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
    left, right = 0, len(nums)-1
    mid = (left + right) // 2
    left_list = merge_sort(nums[:mid+1])
    right_list = merge_sort(nums[mid+1:])
    merge_list = merge(left_list, right_list)
    return merge_list

if __name__ == "__main__":
    nums = [44, 23, 10, 21, 32, 78, 50, 9, 0, -4]
    new_nums = merge_sort(nums)
    print(new_nums)```

[krahets]

时间和空间都会有些影响，因为在递归过程中会反复对数组进行切片（创建新的数组）

[checkma-xh]

def merge(nums, left, mid, right):
    i, j = left, mid + 1
    tmp_array = []
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp_array.append(nums[i])
            i += 1
        else:
            tmp_array.append(nums[j])
            j += 1
    
    if i <= mid:
        tmp_array.extend(nums[i:mid + 1])
    else:
        tmp_array.extend(nums[j:right + 1])
    
    nums[left:right + 1] = tmp_array


def sort(nums, left, right):
    if left >= right:
        return
    
    mid = (right + left) // 2
    sort(nums, left, mid)
    sort(nums, mid + 1, right)
    merge(nums, left, mid, right)


nums = [1,3,32,4,1,-100,23,17,23,6,-7,2,9,-1000]
left = 0
right = len(nums) - 1

sort(nums, left, right)
print(nums)

[syutengu]

js的一些文字游戏。效率肯定不比原文。但对我来说，更容易写。

    /* 合并左右子数组 */
    function merge(l, m, r) {
      // 记录初始l和m
      const init = { l, m }
      // 临时数组
      const arr = []
      // 向右移动指针l和m，当左右子数组均非空时，比较nums[l]和nums[m+1]大小，取较小者加入临时数组尾部
      while (l <= init.m && m + 1 <= r) arr.push(nums[
        nums[l] <= nums[m + 1] ? l++ : m++ + 1
      ])
      // 原数组[l,r]区间，使用[...临时数组,...左子数组残部,...右子数组残部]替换之
      nums.splice(//in-place replacing
        init.l,//start
        r - init.l + 1,//delete count
        ...arr,//new items
        ...nums.slice(l, init.m + 1),//new items
        ...nums.slice(m + 1, r + 1),//new items
      )
    }

[RusselLeekok]

js牛皮

[yuanlongdong]

归并排序单链表：
使用自底向上的方法实现归并排序，则可以达到 O(1) 的空间复杂度。

首先求得链表的长度 length，然后将链表拆分成子链表进行合并。

具体做法如下。

用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。

每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。

将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。

如何保证每次合并之后得到的子链表都是有序的呢？可以通过数学归纳法证明。

初始时 subLength=1，每个长度为 1 的子链表都是有序的。

如果每个长度为 subLength 的子链表已经有序，合并两个长度为 subLength 的有序子链表，得到长度为 subLength×2 的子链表，一定也是有序的。

当最后一个子链表的长度小于 subLength 时，该子链表也是有序的，合并两个有序子链表之后得到的子链表一定也是有序的。

因此可以保证最后得到的链表是有序的。
#include

using namespace std;

struct ListNode
{
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int v) : val(v), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
ListNode* sortList(ListNode* head)
{
if (!head || !head->next)
{
return head;
}

    ListNode* tmp = head;
    int length = 0;

    while (tmp)
    {
        length++;
        tmp = tmp->next;
    }

    ListNode* dummy = new ListNode(0, head);
    for (int subLength = 1; subLength < length; subLength <<= 1)
    {
        ListNode* curr = dummy->next;
        ListNode* tail = dummy;

        while (curr)
        {
            ListNode* left = curr;
            ListNode* right = split(left, subLength);
            curr = split(right, subLength);

            tail->next = merge(left, right);

            // 更新 tail 指向最后一个节点
            while (tail->next)
            {
                tail = tail->next;
            }
        }
    }

    ListNode* ans = dummy->next;
    delete dummy; // 释放哨兵节点

    return ans;
}

private:
ListNode* split(ListNode* head, int size)
{
for (int i = 1; head && i < size; i++)
{
head = head->next;
}

    if (!head) return nullptr;
    ListNode* nextHead = head->next;
    head->next = nullptr;

    return nextHead;
}

ListNode* merge(ListNode* head1, ListNode* head2)
{
    ListNode* dummy = new ListNode(0);
    ListNode* pre = dummy;
    ListNode* l1 = head1;
    ListNode* l2 = head2;

    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            pre->next = l1;
            l1 = l1->next;
        }
        else
        {
            pre->next = l2;
            l2 = l2->next;
        }

        pre = pre->next;
    }

    if (l1)
    {
        pre->next = l1;
    }

    if (l2)
    {
        pre->next = l2;
    }

    ListNode* ans = dummy->next;
    delete dummy; // 释放临时节点
    return ans;
}

};

void deleteList(ListNode* head) {
while (head) {
ListNode* temp = head;
head = head->next;
delete temp; // 释放节点
}
}

int main()
{
ListNode* n1 = new ListNode(-1);
ListNode* n2 = new ListNode(5, n1);
ListNode* n3 = new ListNode(3, n2);
ListNode* n4 = new ListNode(4, n3);
ListNode* n5 = new ListNode(0, n4);

Solution s;
ListNode* ans = s.sortList(n5);

while (ans)
{
    cout << ans->val << " ";
    ans = ans->next;
}

cout << endl;

// 释放排序后的链表
deleteList(ans);

return 0;

}

[leila-huang]

谢谢分享！
我参考 被删的前端游乐场 分享的归并排序实现来加深理解，这个js实现我比较好理解

function mergeSort(nums) {

 const len = nums.length
 // 递归结束边界

 // 交换顺序
 if(len===2&&len[0]>len[1]){
  return [len[1],len[0]]
 }
 if(len<2)return nums

 //  取出中间index
 const mid = parseInt(len/2)
 //  slice 会提取到但不包括 end 的位置。left是0~mid~1,right是mid~结束
 const left = mergeSort(nums.slice(0,mid))
 const right = mergeSort(nums.slice(mid))
 let newArr = []
 for (let i = 0; i < len; i++) {
  // 左右两边不一定有值,将有值的加到新数组尾部
  if(!left.length||!right.length){
   newArr = newArr.concat(left.length===0?right:left)
   break
  }
  // 左右都有值,判断左右两边最小的值，并加到新数组中
  newArr.push(left[0]>=right[0]?right.splice(0,1)[0]:left.splice(0,1)[0])
 }
 return newArr
}

[MoRongsi]

js中一个理解起来更简单的写法：

// 拆分
function mergeSort(arr) {
  let len = arr.length;
  if(len < 2) {
    return arr;
  }
  let middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

// 合并
function merge(left, right){
  let result = [];
// 左右子树非空时
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
// 存在空子树就已经拍好序了，再把剩下的push进去
  result.push(...left);
  result.push(...right);
  return result;
}

[FrierenGreatDemonLord]

Python 利用列表的追加合并简化代码：

def merge(arr: list[int], l: int, m: int, r: int):
    temp = []
    i, j = l, m + 1
    # merge two sorted sub-arrays into one sorted array
    while i <= m and j <= r:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    # append remaining elements of the sub-arrays
    if i <= m:
        temp += arr[i: m + 1]
    if j <= r:
        temp += arr[j: r + 1]
    # copy the sorted array back to the original array
    for i, val in enumerate(temp):
        arr[l + i] = val

[FrierenGreatDemonLord]

也可省去追加残余数组元素的判断

def merge(arr: list[int], l: int, m: int, r: int):
    temp = []
    i, j = l, m + 1
    # merge two sorted sub-arrays into one sorted array
    while i <= m and j <= r:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    # append remaining elements of the sub-arrays
    temp += arr[i: m + 1]
    temp += arr[j: r + 1]
    # copy the sorted array back to the original array
    for i, val in enumerate(temp):
        arr[l + i] = val

[Mrstarer]

时间复杂度每层合并时的每次操作时间视为单位时间，则考虑操作次数，容易从合并代码的三次循环发现需要遍历完数组，或者说遍历数组的次数与数组长度n成正比，故每层时间复杂度为O(n),而递归操作次数与log2n成正比，所以最后为O(nlogn)；而空间复杂度从栈帧空间来看的话，最深时为logn，每回溯一层到上一层就释放一次栈，然后记录一次合并的tmp，然后继续右子数组递归往下，然后递归到底又回溯重复许多这样的操作，直至回到第一层此时已完成左子数组的排序(记录下了一半的nums），栈帧空间只有一层的内容(都释放完了），然后重复左子数组的行为开始递归右子数组，最后得到另一半的nums，执行第一层的归并排序代码merge(nums, left, mid, right)。从整个流程来看，栈帧空间最大为logn，临时数组tmp最大为n(执行第一层的归并排序代码merge(nums, left, mid, right)时产生的临时数组tmp），取最大故O(n)。

[FrierenGreatDemonLord]

C 可用3元运算符简化处理左右子数组处的代码

while (i <= m && j <= r)
	temp[size++] = arr[i] < arr[j]? arr[i++] : arr[j++];

[1hew]

def merge_sort(nums: list[int]):
"""
空间优化归并排序
只创建一个大小为 n 的临时数组
"""
# 时间复杂度 O(nlogn)
# 空间复杂度 O(n)

n = len(nums)
# 处理空数组或单元素数组
if n <= 1:
    return nums

# 创建临时数组，避免在递归过程中重复创建
temp = [0] * n

def sort(arr, left, right, temp):
    """递归排序函数"""
    # 递归终止条件：当子数组长度为 1 时
    if left >= right:
        return

    # 计算中间点，将数组分为两半
    mid = (left + right) // 2
    # 递归排序左半部分
    sort(arr, left, mid, temp)
    # 递归排序右半部分
    sort(arr, mid + 1, right, temp)

    # 如果数组已经有序，直接返回
    # 判断左半部分的最大值是否小于等于右半部分的最小值
    if arr[mid] <= arr[mid + 1]:
        return

    # 合并两个有序数组的过程
    i, j = left, mid + 1  # i 指向左半部分，j 指向右半部分
    # 将左半部分复制到临时数组，右半部分已经在原数组中
    temp[left: mid + 1] = arr[left: mid + 1]

    # 比较左右两部分的元素，将较小的放入原数组
    for k in range(left, right + 1):
        if i > mid:  # 左半部分用完了，退出循环（右半部分已在正确位置）
            break
        elif j > right:  # 右半部分用完了，将左半部分剩余元素复制回原数组
            arr[k] = temp[i]
            i += 1
        elif temp[i] <= arr[j]:  # 左半部分当前元素更小
            arr[k] = temp[i]
            i += 1
        else:  # 右半部分当前元素更小
            arr[k] = arr[j]
            j += 1

# 调用递归排序函数
sort(nums, 0, n - 1, temp)
return nums

nums = [1, 3, 32, 4, 1, -100, 23, 17, 23, 6, -7, 2, 9, -1000]
print(merge_sort(nums))