归并排序

归并排序体现的是分治的思想，将一个数组一分为二，剩余的两部分再一分为二，以此递归，直到不能分解为止。然后顺序合并，合并的过程中，比较要合并的两端，形成一个新的有序数组。

代码实现

直接修改原数组的方式

"""
    归并排序
    Author: xingrui
"""


# 归并排序 - 正序
def mergeSort2(nums: list, p: int, r: int, direction: str):
    if p >= r:
        return

    q = int((r + p) / 2)
    mergeSort2(nums, p, q, direction)
    mergeSort2(nums, q + 1, r, direction)
    merge(nums, p, q , r, direction)


# 合并数组
def merge(nums: list, p: int, q: int, r: int, direction: str):
    i = p
    j = q + 1
    res = []

    if direction == 'asc':
        while i <= q and j <= r:
            if nums[i] <= nums[j]:
                res.append(nums[i])
                i += 1
            else:
                res.append(nums[j])
                j += 1
    else:
        while i <= q and j <= r:
            if nums[i] >= nums[j]:
                res.append(nums[i])
                i += 1
            else:
                res.append(nums[j])
                j += 1

    while i <= q:
        res.append(nums[i])
        i += 1

    while j <= r:
        res.append(nums[j])
        j += 1

    while p <= r:
        nums[p] = res[0]
        p += 1
        res = res[1:]


if __name__ == "__main__":
    nums = [4, 5, 2, 6, 2, 3, 9, 3, 1, 20, 57, 39]
    p, q = 0, len(nums) - 1
    mergeSort2(nums, p, q, 'asc')
    print('归并排序，正序排列', nums)
    mergeSort2(nums, p, q, 'desc')
    print('归并排序，逆序排列', nums)

生成新数组

"""
    归并排序
    Author: xingrui
"""


# 归并排序 - 正序
def mergeSort(nums: list, direction: str) -> list:
    if len(nums) <= 1:
        return nums
    else:
        mid = int(len(nums) / 2)
        left = mergeSort(nums[:mid], direction)
        right = mergeSort(nums[mid:], direction)
        return merge(left, right, direction)


# 合并数组
def merge(left: list, right: list, direction: str) -> list:
    res = []

    if direction == 'asc':
        while left and right:
            minValue = left[0]
            if left[0] < right[0]:
                left = left[1:]
            else:
                minValue = right[0]
                right = right[1:]

            res.append(minValue)
    else:
        while left and right:
            maxValue = left[0]
            if left[0] > right[0]:
                left = left[1:]
            else:
                maxValue = right[0]
                right = right[1:]

            res.append(maxValue)

    res += left if left else right
    return res

# 合并数组
# def merge(left: list, right: list, direction: str) -> list:
#     res = []
#
#     if direction == 'asc':
#         while left and right:
#             minValue = left[0]
#             if left[0] < right[0]:
#                 left.remove(left[0])
#             else:
#                 minValue = right[0]
#                 right.remove(right[0])
#
#             res.append(minValue)
#     else:
#         while left and right:
#             maxValue = left[0]
#             if left[0] > right[0]:
#                 left.remove(left[0])
#             else:
#                 maxValue = right[0]
#                 right.remove(right[0])
#
#             res.append(maxValue)
#
#     res += left if left else right
#     return res

# 合并数组
# def merge(left: list, right: list, direction: str) -> list:
#     res = []
#
#     if direction == 'asc':
#         while left and right:
#             minValue = left.pop(0) if left[0] < right[0] else right.pop(0)
#             res.append(minValue)
#     else:
#         while left and right:
#             maxValue = left.pop(0) if left[0] > right[0] else right.pop(0)
#             res.append(maxValue)
#
#     res += left if left else right
#     return res


if __name__ == "__main__":
    nums = [4, 5, 2, 6, 2, 3, 9, 3, 1, 20, 57, 39]
    print('归并排序，正序排列', mergeSort(nums, 'asc'))
    print('归并排序，逆序排列', mergeSort(nums, 'desc'))

分析

时间复杂度

归并排序是使用递归实现的，推导排序的时间复杂度不太容易。可以先列个公式：
T(n) = 2 * T(n/2) + n

其中T(n)是整个归并排序所需要花费的时间，归并排序需要将数组一分为二，分开部分排序需要的时间为T(n/2)，最后的n是当数组分到不可再分的时候，这个时候就需要merge所有最小片段，这个过程的时间复杂度为O(n)。

得到了公式，我们就可以按照归并排序的规则——一分为二，继续分解公式
T(n) = 2 * T(n/2) + n
T(n) = 2 * 2 * T(n/4) + 2n = 4 * T(n/4) + 2n
T(n) = 4 * 2 * T(n/8) + 3n = 8 * T(n/8) + 3n
T(n) = 8 * 2 * T(n/16) + 4n = 16 * T(n/16) + 4n
..............
T(n) = $2^k * T(\frac{n}{2^k}) + k * n$

上面的式子一直分解，直到T(n) = 1的时候不再分解，此时 $T(\frac{n}{2^k}) == 1$ ，
则 $k = \log_2{n}$ ，然后将k代入上面的公式
$2^k * T(\frac{n}{2^k}) + k * n$
$2^{\log_2{n}} * T(\frac{n}{2^{\log_2{n}}}) + {\log_2{n}} * n$
$C * n + n * {\log_2{n}}$

根据时间复杂度的最大原则， $n * {\log_2{n}}$ 大于 n，则归并排序的时间复杂度为 $n * {\log{n}}$

空间复杂度

归并排序的空间复杂度为O(n)，因为在合并的时候需要一个新数组来装临时数据，这个数组的长度最大不会超过数组长度n

是否稳定

归并排序是稳定的排序算法，决定其是否稳定的代码在合并函数中

        while i <= q and j <= r:
            if nums[i] <= nums[j]:
                res.append(nums[i])
                i += 1
            else:
                res.append(nums[j])
                j += 1

只要确保遇到相等的值，总是优先取左边的数据，该算法就是稳定的。

文章参考

https://blog.csdn.net/czg13548930186/article/details/72860942
https://www.jianshu.com/p/22e7d281859e
https://oiltang.com/2014/05/04/markdown-and-mathjax/
https://time.geekbang.org/column/article/41913

Python实现归并排序