#!/usr/bin/python
# -*- coding: utf-8 -*-

class Ch06_08(object):
    
    def __init__(self, data):
        self.count = 0
        self.array = data
        self.merge_sort(0, len(data) - 1)

    def merge_sort(self, left, right):
        if (left < right):
            # 先找中間的位置
            half = (left + right) // 2
            # 將左邊到中間的一半數列作排序
            self.merge_sort(left, half)
            # 將中間到右邊的一半數列作排序
            self.merge_sort(half + 1, right)
            # 將左右兩個數列合併
            self.merge(left, left, half, half + 1, right)
            self.count += 1
            # 印出
            self.travel(self.count, left, right)

    def merge(self, A1_start, A2_start, A2_end, A3_start, A3_end):
        k = 0
        B = []

        i1 = A2_start
        i2 = A2_end

        j1 = A3_start
        j2 = A3_end
        
        # 泡沫排序法
        while ((i1 <= i2) and (j1 <= j2)):
            if (self.array[i1] <= self.array[j1]):
                B.append(self.array[i1])
                i1 += 1
            else:
                B.append(self.array[j1])
                j1 += 1

        # 剩餘補後面
        while (i1 <= i2):
            B.append(self.array[i1])
            i1 += 1
        
        # 剩餘補後面
        while (j1 <= j2):
            B.append(self.array[j1])
            j1 += 1

        for h in B:
            self.array[A1_start+k] = h
            k += 1

    def travel(self, count, left, right):
        j = 0
        print("# %d ==>" % count, end="")
        for i in self.array:
            if (j == left): print("[", end=" ")
            print("%d" % i, end=" ")
            if (j == right): print("]", end=" ")
            j += 1

        print()

    # 最後印出
    def end(self):
        return self.array

if __name__ == '__main__':
    a = [4, 67, 14, 90, 125, 89, 231, 2, 51]
    xx = Ch06_08(a)
