"""
归并排序：类似快排，通过不断将列表折半来进行排序。
如果集合为空或只有一个项，则按基本情况排序。
如果有多项，则分割集合，并递归调用两个区间的归并排序。
一旦对这两个区间排序完成，就执行合并操作。
"""


def merge_sort(nums: list[int], left: int, right: int, ):
    if left >= right:
        return

    mid = (left + right) >> 1
    merge_sort(nums, left, mid)
    merge_sort(nums, mid + 1, right)
    merge(nums, left, mid, right)


def merge(nums: list[int], left: int, mid: int, right: int):
    # 临时数组存放合并后的结果
    temp = [0] * (right - left + 1)

    # 初始化左、右字序列的起始索引，左从left开始，右从mid开始
    i, j, k = left, mid + 1, 0

    # 左边第一个肯定是左边最小的，右边第一个肯定是右边最小的
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            temp[k] = nums[i]
            i += 1
        else:
            temp[k] = nums[j]
            j += 1

        k += 1

    # 比较终结时，可能由于对折不均，仍有一边右数没有添加到临时列表中
    while i <= mid:
        temp[k] = nums[k]
        i += 1
        k += 1

    while j <= right:
        temp[k] = nums[j]
        j += 1
        k += 1

    # 将临时数组中的元素复制回原数组对应的位置
    for k in range(len(temp)):
        nums[left + k] = temp[k]