# Merge Sort合併排序
###### tags: `Algorithm` `Datastruction`


使用了演算法策略divide-and-conquer，將原本問題分為兩個子問題，一個比基準值小，一個比基準值大，再分別解決各自子問題，且在子問題中利用遞迴使用相同演算法來解決問題。

python code:

# -*- coding: utf-8 -*-
from __future__ import print_function

def quick_sort(data):
    size = 0
    i = 0

    print('\nPlease enter number to sort (enter 0 when end): ') # 要求輸入資料直到輸入為零
    while True:
        i += 1
        data.append(int(input('#%d number: ' % i)))
        if data[size] == 0:#輸入0跳出
            break
        size += 1

    for i in range(60):
        print('-', end = '')
    print()

    sorting(data, 0, size-1, size)#進入另個程式區塊

    for i in range(60):
        print('-', end = '')

    print('\nFinal sorted data: ', end = '')
    for i in range(size):
        print(data[i], ' ', end = '')

def sorting(data, left, right, size):
    #left與right分別代表整個資料的兩端，以首data當成基準值
    if left < right:
        lbase = left + 1#以第二筆作為初始lbase
        while data[lbase] < data[left]:#向右移動，與基準值做比較
            if lbase+1 > size:
                break
            lbase += 1
        rbase = right#最後一筆作為初始rbase
        while data[rbase] > data[left]:#向左移動，與基準值做比較
            rbase -= 1
        while lbase < rbase: # 若lbase小於rbase，注意這裡是index，則將兩筆的資料對調
            data[lbase], data[rbase] = data[rbase], data[lbase]
            lbase += 1#lbase向右移動
            while data[lbase] < data[left]:#若小於基準值，則繼續往右找
                lbase += 1
            rbase -= 1
            while data[rbase] > data[left]:#若大於left的值，則繼續往左找
                rbase -= 1
        data[left], data[rbase] = data[rbase], data[left] # 此時lbase大於rbase，則rbase的資料與第一筆對調
        
        print('Sorting: ', end = '')
        for i in range(size):
            print('%4d' % data[i], end = '')
        print()
        #divide-and-conquer：分為兩個子循環，一個是基準值左邊，一個是基準值右邊
        sorting(data, left, rbase-1, size)#排左邊(遞迴)
        sorting(data, rbase+1, right, size)#排右邊(遞迴)

def main():
    data = []
    quick_sort(data)

main()
8