归并排序

"""
归并排序思想：
（1）把数组nums[]分为左右两个数组，nums[left,mid],nums[mid+1,right]
当划分的两数组left>=right的时候，则需要合并两数组了。
（2）合并两数组，先定义一个临时数组temp，每次分别从
nums[left,mid],nums[mid+1,right]取较小的那个，然后被取的数组指针i++；
最终把临时数组的值重新赋值给合并的数组nums[]
"""
class Solution:
    def mergeSort(self,arr):
        self.mSort(arr,0,len(arr)-1)

    def mSort(self,arr,left,right):
        if left>=right:
            return
        mid = int((left+right)/2)

        self.mSort(arr,left,mid)
        self.mSort(arr,mid+1,right)
        self.merge(arr,left,mid,right)

    def merge(self,arr,left,mid,right):
        temp = [0]*(right-left+1)
        i = left
        j = mid+1
        k = 0
        while i<=mid and j<=right:
            if arr[i]<=arr[j]:
                temp[k]=arr[i]
                k+=1
                i+=1
            else:
                temp[k]=arr[j]
                k+=1
                j+=1
        while i<=mid:
            temp[k]=arr[i]
            k+=1
            i+=1
        while j<=right:
            temp[k]=arr[j]
            k+=1
            j+=1
        for i in range(len(temp)):
            arr[left+i]=temp[i]

if __name__=="__main__":
    so = Solution()
    arr = [2,3,6,1,9]
    so.mergeSort(arr)
    print(arr)