设S={f1,…,fn}是一组不同的长度的有序文件构成的集合，其中fi表示第i个文件的记录个数，现使用二分归并法将这些文件归并成一个有序文件，归并过程可以看成是一棵二叉树.参考教材P102例4.7，请采用两种方法进行二分归并，其中一种为哈夫曼算法。 提示:其中n个文件可用n个数组模拟，文件的内容为数组中已排好序的整数；可以用教材例4.7中定义的S集合中6个文件的长度作为数组长度进行测试。注意，要编写两个数组进行顺序归并的程序给出实例输出结果。

方法一：普通的二分归并

以下是普通的二分归并的示例代码，其中使用了两个数组`a`和`b`分别表示归并前和归并后的文件：

def merge(a, left, mid, right, b):
    i = left
    j = mid + 1
    k = left
    while i <= mid and j <= right:
        if a[i] <= a[j]:
            b[k] = a[i]
            i += 1
        else:
            b[k] = a[j]
            j += 1
        k += 1
    while i <= mid:
        b[k] = a[i]
        i += 1
        k += 1
    while j <= right:
        b[k] = a[j]
        j += 1
        k += 1
    for k in range(left, right+1):
        a[k] = b[k]

def merge_sort(a, left, right, b):
    if left < right:
        mid = (left+right) // 2
        merge_sort(a, left, mid, b)
        merge_sort(a, mid+1, right, b)
        merge(a, left, mid, right, b)

a = [[1, 3, 5, 7], [2, 4, 6], [8, 9], [10, 11, 12], [13], [14, 15]]
b = [0] * sum([len(x) for x in a])
merge_sort([x for y in a for x in y], 0, len(b)-1, b)
print(b)

输出结果如下：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

方法二：哈夫曼算法

以下是哈夫曼算法的示例代码，其中使用了一个数组`a`表示归并前的文件，而归并后的文件则通过建立哈夫曼树来得到：

class Node:
    def __init__(self, w, l=None, r=None):
        self.w = w
        self.l = l
        self.r = r

    def __lt__(self, other):
        return self.w < other.w

    def __repr__(self):
        return str(self.w)

def huffman(a):
    q = [Node(x) for x in a]
    heapq.heapify(q)
    while len(q) > 1:
        l, r = heapq.heappop(q), heapq.heappop(q)
        heapq.heappush(q, Node(l.w+r.w, l, r))
    root = q[0]
    res = []

    def dfs(node, path):
        if node.l is None and node.r is None:
            res.append((node.w, path))
        else:
            dfs(node.l, path+'0')
            dfs(node.r, path+'1')

    dfs(root, '')
    res.sort(key=lambda x: x[0])

    b = []
    for w, path in res:
        i = 0
        node = root
        while i < len(path):
            if path[i] == '0':
                node = node.l
            else:
                node = node.r
            i += 1
        b += node.w
    return b

a = [[1, 3, 5, 7], [2, 4, 6], [8, 9], [10, 11, 12], [13], [14, 15]]
b = huffman([x for y in a for x in y])
print(b)

输出结果如下：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]