Sort-JZTXT

class Solution:
    def merge(self, arr, l, m, r):
        # the length of the left and the right
        n1 = m - l + 1
        n2 = r - m

        # 创建临时数组
        L = [0] * (n1)
        R = [0] * (n2)

        # 拷贝数据到临时数组 arrays L[] 和 R[]
        for i in range(0, n1):
            L[i] = arr[l + i]

        for j in range(0, n2):
            R[j] = arr[m + 1 + j]

            # 归并临时数组到 arr[l..r]
        i = 0  # 初始化第一个子数组的索引
        j = 0  # 初始化第二个子数组的索引
        k = l  # 初始归并子数组的索引

        while i < n1 and j < n2:
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 拷贝 L[] 的保留元素
        while i < n1:
            arr[k] = L[i]
            i += 1
            k += 1

        # 拷贝 R[] 的保留元素
        while j < n2:
            arr[k] = R[j]
            j += 1
            k += 1

    def mergeSort(self, arr, l, r):
        if l < r:
            m = l + (r - l) // 2

            self.mergeSort(arr, l, m)
            self.mergeSort(arr, m + 1, r)
            self.merge(arr, l, m, r)



if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6, 7]
    n = len(arr)

    print("给定的数组")
    for i in range(n):
        print("%d" % arr[i]),

    solution = Solution()
    result = solution.mergeSort(arr, 0, n - 1)

    print("\n\n排序后的数组")
    for i in range(n):
        print("%d" % arr[i])