【算法日积月累】5-自底向上的归并排序

自底向上的归并排序-1

下面我们使用一种全新的思路来实现归并排序算法。

自底向上的归并排序-2

由于少了递归，我们只保留了“合并两个有序”数组的代码。

Python 代码：

def __merge_of_two_sorted_array(nums, left, mid, right):
    for index in range(left, right + 1):
        nums_for_compare[index] = nums[index]
    i = left
    j = mid + 1
    for k in range(left, right + 1):
        if i == mid + 1:
            nums[k] = nums_for_compare[j]
            j += 1
        elif j > right:
            nums[k] = nums_for_compare[i]
            i += 1
        elif nums_for_compare[i] < nums_for_compare[j]:
            nums[k] = nums_for_compare[i]
            i += 1
        else:
            assert nums_for_compare[i] >= nums_for_compare[j]
            nums[k] = nums_for_compare[j]
            j += 1


def merge_sort(nums):
    l = len(nums)
    global nums_for_compare
    nums_for_compare = list(range(l))
    sz = 1
    # sz = 1, 2, 4, 8
    while sz < l:
        # left = 0, 2, 4, 6
        left = 0
        while left < l - sz:
            __merge_of_two_sorted_array(nums, left, left + sz - 1, min(left + sz + sz - 1, l - 1))
            left += 2 * sz
        sz *= 2

说明：“自底向上”的归并排序，因为没有使用到数组元素能够快速索引这个特性，因此很适合于链表这种数据结构。为此我曾经写过一个 LeetCode 第 148 题题解，下面的图展示了这种思路。

自底向上的归并排序-3

自底向上的归并排序-4

自底向上的归并排序-5

自底向上的归并排序-6

自底向上的归并排序-7

自底向上的归并排序-8

自底向上的归并排序-9

当然，我觉得这道题的常规做法还是“自顶向下”的归并排序，使用分治的思想完成。

传送门：LeetCode 第 148 题：排序链表。

英文网址：148. Sort List ，中文网址：148. 排序链表 。

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

本文源代码

Python：代码文件夹，Java：代码文件夹。

（本节完）