歸并排序及python遞歸實作

歸并排序的思想可用分而治之概括，可由下圖生動的诠釋。圖檔來自https://www.cnblogs.com/chengxiao/p/6194356.html

python代碼：

歸并排序，分而治之
'''

def merge(list1,list2): #将兩個有序數組融合
    ls=[]
    i=j=0
    while i<len(list1) and j<len(list2):

        if list1[i]<list2[j]:
            ls.append(list1[i])
            i+=1
        else:
            ls.append(list2[j])
            j+=1

    while i<len(list1):
        ls.append(list1[i])
        i+=1

    while j< len(list2):
        ls.append(list2[j])
        j+=1
    return ls

def merge_sort(lists): #遞歸将原數組拆分并排序
    if len(lists)<=1:
        return lists
    middle = int(len(lists)/2)
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left,right)

if __name__=='__main__':

    a=[1,9,7,3,10,21,12,3,4,7]

    print(merge_sort(a))