[python-merge-sort] merge sort template #python #algorithm

merge_sort.py

def reversePairs_using_merge_sort(nums):
    n = len(nums)
    buffer = [None] * n

    # 最本质的方法其实应该想到使用merge_sort，因为天然的思考过程可以考虑到分为两个部分
    # reversePairs的个数等于左边reverse的和右边reverse的，然后加上合并过程中reverse的
    # 这和merge_sort的过程不谋而和。实现的过程中，控制左边变量i的移动，每次找到一个i
    # 不停的移动p指针找到符合要求节点的上限，使用j指针找到比i节点小的节点上限，合并和
    # 计算reverse pair过程重叠，非常nice的solution
    def merge_sort_impl(l, r):
        if l >= r: return 0

        m = l + ((r-l)>>1)
        res = merge_sort_impl(l, m) + merge_sort_impl(m+1, r)

        i, j, p, k = l, m+1, m+1, 0
        while i <= m:
            while p <= r and nums[i] > nums[p]*2: p+=1
            res += p-m-1

            # 后面的小，取后面先
            while j <= r and nums[i] > nums[j]: buffer[k], j, k = nums[j], j+1, k+1

            # 左边的小，取前面节点
            buffer[k], k, i = nums[i], k+1, i+1

        # j剩余的元素不需要复制，只需要将前K个元素复制过来即可
        nums[l:l+k] = buffer[:k]
        return res

    return merge_sort_impl(0, n-1)