import random
#生成指定個(gè)數(shù)的隨機(jī)數(shù)組
def gen_random_list(num):
    if num<1:
        return []
    return [random.randint(1,100) for _ in range(num)]

"""
歸并的結(jié)果存儲(chǔ)到原數(shù)組
索引為low~mid范圍的元素是有序的
索引為mid+1~high范圍的元素是有序的
"""
class Merg_Sort:
    def _merg(self,array,low,mid,high):
        print('_merg low:{} mid:{} high:{}'.format(low,mid,high)) #打印這句話是為了跟蹤棧的軌跡
        left_index=low
        right_index=mid+1

        k=low
        while k<=high:
            self.temp_list[k]=array[k]
            k+=1

        k=low
        while k<=high:
            if left_index>mid: #左半邊有序子列已經(jīng)遍歷完了
                array[k]=self.temp_list[right_index]
                right_index+=1
            elif right_index>high: #右半邊有序子列已經(jīng)遍歷完了
                array[k]=self.temp_list[left_index]
                left_index+=1
            elif self.temp_list[left_index]<=self.temp_list[right_index]: #就是當(dāng)前左右指針?biāo)赶虻挠野脒呍卮笥谧蟀脒呍?                array[k]=self.temp_list[left_index]
                left_index+=1
            else:    # self.temp_list[left_index]>self.temp_list[right_index] 就是當(dāng)前左右指針?biāo)赶虻淖蟀脒呍卮笥谟野脒呍?                array[k]=self.temp_list[right_index]
                right_index+=1
            k+=1


    def sort(self,random_list,non_recursive=False):
        self.temp_list=[_ for _ in random_list]
        if non_recursive:
            self._sort_non_recursive(random_list)
        else:
            self._sort_recursive(random_list,0,len(random_list)-1)

    def _sort_non_recursive(self,array):
        array_len=len(array)
        size=1
        while size<=array_len:
            low=0
            print('_sort_non_recursive size:{}'.format(size)) #觀察棧的軌跡
            while low<array_len-size:
                mid=low+size-1
                high=low+2*size-1 if low+2*size-1 <= array_len-1 else array_len-1

                self._merg(array,low,mid,high)

                low+=(size*2)
            size*=2
"""
輸入為:
    original_list=gen_random_list(5)
    print('----------------------unsort original_list:{}-----------------'.format(original_list))
    Merg_Sort().sort(original_list,non_recursive=True)
    print('------------------------sort original_list:{}-----------------'.format(original_list))
輸出為:
    ----------------------unsort original_list:[19, 50, 20, 11, 14]-----------------
        _sort_non_recursive size:1
        |    |
        |    |_merg low:0 mid:0 high:1  [0,1]有序,此時(shí)size為1
        |    |_merg low:2 mid:2 high:3  [2,3]有序,此時(shí)size為1
        |    |
        |_sort_non_recursive size:2
        |    |
        |    |_merg low:0 mid:1 high:3  [0,3]有序,此時(shí)size為2
        |    |
        |_sort_non_recursive size:4
        |    |
        |    |_merg low:0 mid:3 high:4  [0,4]有序,此時(shí)size為4
        |    |
        |    |
棧指針   0    1
    ------------------------sort original_list:[11, 14, 19, 20, 50]-----------------
"""
"""
輸出為:
    ----------------------unsort original_list:[18, 72, 43, 94, 62, 57, 26, 55, 34, 79]-----------------
        _sort_non_recursive size:1
       |     |
       |     |_merg low:0 mid:0 high:1 [0,1]有序,此時(shí)size為1
       |     |_merg low:2 mid:2 high:3 [2,3]有序,此時(shí)size為1
       |     |_merg low:4 mid:4 high:5 [4,5]有序,此時(shí)size為1
       |     |_merg low:6 mid:6 high:7 [6,7]有序,此時(shí)size為1
       |     |_merg low:8 mid:8 high:9 [8,9]有序,此時(shí)size為1
       |     | 
       |_sort_non_recursive size:2
       |     |
       |     |_merg low:0 mid:1 high:3 [0,3]有序,此時(shí)size為2
       |     |_merg low:4 mid:5 high:7 [4,7]有序,此時(shí)size為2
       |     |
       |_sort_non_recursive size:4
       |     |
       |     |_merg low:0 mid:3 high:7 [0,7]有序,此時(shí)size為4
       |     |
       |_sort_non_recursive size:8
       |     |
       |     |_merg low:0 mid:7 high:9 [0,9]有序，此時(shí)size為8
       |     |
       |     |
棧指針  0     1
    ------------------------sort original_list:[18, 26, 34, 43, 55, 57, 62, 72, 79, 94]----------------- 
    
"""

    def _sort_recursive(self,array,low,high):
        print('_sort_recursive    low:{} high:{}'.format(low,high)) #打印這句話是為了跟蹤棧的軌跡
        if low>=high:
            return
        mid=low+int( (high-low)/2 )
        self._sort_recursive(array,low,mid) #將左半邊排序
        self._sort_recursive(array,mid+1,high) #將右半邊排序
        self._merg(array,low,mid,high) #歸并結(jié)果

'''
輸入如此:
    original_list=gen_random_list(5)
    print('----------------------unsort original_list:{}-----------------'.format(original_list))
    Merg_Sort().sort(original_list)
    print('------------------------sort original_list:{}-----------------'.format(original_list))
    
輸出如下:
    ----------------------unsort original_list:[94, 33, 21, 56, 92]-----------------
        _sort_recursive    low:0 high:4
        |
        |    _sort_recursive    low:0 high:2
        |    |   |
        |    |   |_sort_recursive    low:0 high:1
        |    |   |    |
        |    |   |    |_sort_recursive    low:0 high:0
        |    |   |    |_sort_recursive    low:1 high:1
        |    |   |    |_merg low:0 mid:0 high:1
        |    |   |    |
        |    |   |_sort_recursive    low:2 high:2
        |    |   |    |
        |    |   |_merg low:0 mid:1 high:2
        |    |   |    |
        |    |_sort_recursive    low:3 high:4
        |    |   |    |
        |    |   |_sort_recursive    low:3 high:3
        |    |   |_sort_recursive    low:4 high:4
        |    |   |_merg low:3 mid:3 high:4
        |    |   |    |
        |    |_merg low:0 mid:2 high:4
        |    |   |    |
        |    |   |    |
棧指針   0    1   2    3
    ------------------------sort original_list:[21, 33, 56, 92, 94]-----------------
    可見(jiàn)最深的時(shí)候棧為4層


輸入如此:
    original_list=gen_random_list(8)
    print('----------------------unsort original_list:{}-----------------'.format(original_list))
    Merg_Sort().sort(original_list)
    print('------------------------sort original_list:{}-----------------'.format(original_list))
輸出如下:
    ----------------------unsort original_list:[65, 80, 99, 41, 76, 40, 71, 68]-----------------
        _sort_recursive    low:0 high:7
        |   |
        |   |_sort_recursive    low:0 high:3
        |   |    |
        |   |    |_sort_recursive    low:0 high:1
        |   |    |    |
        |   |    |    |_sort_recursive    low:0 high:0
        |   |    |    |_sort_recursive    low:1 high:1
        |   |    |    |_merg low:0 mid:0 high:1
        |   |    |    | 
        |   |    |_sort_recursive    low:2 high:3
        |   |    |    |_sort_recursive    low:2 high:2
        |   |    |    |_sort_recursive    low:3 high:3
        |   |    |    |_merg low:2 mid:2 high:3
        |   |    |    |     
        |   |    |_merg low:0 mid:1 high:3
        |   |    |    |
        |   |_sort_recursive    low:4 high:7
        |   |    |    | 
        |   |    |_sort_recursive    low:4 high:5
        |   |    |    | 
        |   |    |    |_sort_recursive    low:4 high:4
        |   |    |    |_sort_recursive    low:5 high:5
        |   |    |    |_merg low:4 mid:4 high:5
        |   |    |    | 
        |   |    |_sort_recursive    low:6 high:7
        |   |    |    | 
        |   |    |    |_sort_recursive    low:6 high:6
        |   |    |    |_sort_recursive    low:7 high:7
        |   |    |    |_merg low:6 mid:6 high:7
        |   |    |    | 
        |   |    |_merg low:4 mid:5 high:7
        |   |    |    |
        |   |_merg low:0 mid:3 high:7
        |   |    |    |
        |   |    |    |
棧指針   0   1    2    3 
    ------------------------sort original_list:[40, 41, 65, 68, 71, 76, 80, 99]-----------------
    可見(jiàn)最深的時(shí)候棧的層數(shù)為4
'''