归并排序的python实现

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。 它将数组分成两个子数组，分别对子数组进行排序，然后合并两个有序的子数组。

算法步骤

1. 递归分解数组，直到子数组的长度为1
2. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
3. 设定两个指针，初始位置分别为两个已经排序序列的起始位置
4. 对比两个指针所指向的元素，选择相对小的元素放入到合并空间
5. 移动指针，直到有一个序列的元素全部处理完毕
6. 合并临时空间中的数据，到原数组中
7. 释放临时空间
8. 向上一层返回

CODE

def merge_sort(arr):
    def merge(left: int, right: int) -> None:
        if left >= right:
            return
        
        mid = (left + right) // 2

        merge(left, mid)
        merge(mid + 1, right)

        i, j = left, mid + 1
        tmp = []

        while i <= mid and j <= right:
            if arr[i] < arr[j]:
                tmp.append(arr[i])
                i += 1
            else:
                tmp.append(arr[j])
                j += 1

        while i <= mid:
            tmp.append(arr[i])
            i += 1

        while j <= right:
            tmp.append(arr[j])
            j += 1

        arr[left:right+1] = tmp
    merge(0, len(arr) - 1)