归并排序

自顶而下

# coding=utf-8
###归并排序
class Merge:
    # 额外数组空间
    aux = []

    def sort(self, arr):
        self.aux = [0] * len(arr)
        self.sort0(arr, 0, len(arr) - 1)

    def sort0(self, arr, low, high):
        if low < high:
            mid = (low + high) // 2
            self.sort0(arr, low, mid)
            self.sort0(arr, mid + 1, high)
            self.merge(arr, low, mid, high)

    def merge(self, arr, low, mid, high):
        for i in range(low, high + 1):
            self.aux[i] = arr[i]
        i = low
        j = mid + 1
        # 原地归并
        for k in range(low, high + 1):
            if i > mid:
                arr[k] = self.aux[j]
                j += 1
            elif j > high:
                arr[k] = self.aux[i]
                i += 1
            elif self.aux[j] >= self.aux[i]:
                arr[k] = self.aux[i]
                i += 1
            else:
                arr[k] = self.aux[j]
                j += 1

自底而上

 def sortBu(self, arr):
        le = len(arr)
        self.aux = [0] * le ##初始化数据大小
        n = 1  # 子列表元素数量
        while n < le:
            for lo in range(0, le - n, 2*n):
                #print("low:"+str(lo))
                hi = min(lo + n + n - 1, le - 1)
                mid = lo + n - 1
                self.merge(arr, lo, mid, hi)
            n = n + n