歸并排序中的合并兩個(gè)有序數(shù)組num1姜盈，num2低千，可以通過比較兩個(gè)數(shù)組中的第一個(gè)元素，取比較小的那個(gè)值馏颂，插入一個(gè)新的數(shù)組栋操，然后繼續(xù)比較剩下的數(shù)值。假設(shè)兩個(gè)數(shù)組的長度分別為m,n ,這樣實(shí)現(xiàn)的空間復(fù)雜度為O(m+n)
如果想要優(yōu)化為空間復(fù)雜度為o(1) （假設(shè)num1的空間足夠容納m+n個(gè)元素）, 可以采用從后往前比較的方式饱亮，將較大的數(shù)字插入num1的尾部矾芙，然后依次往前。
python 實(shí)現(xiàn)：
def merge_sort(array1,array2,m,n):
i ,j =m-1, n-1
k = m+n-1
while i>=0 and j >=0:
if array1[i]>array2[j]:
array1[k]=array1[i]
i-=1
k-=1
else:
array1[k]=array2[j]
j-=1
k-=1
while j>=0:
array1[k]=array2[j]
j-=1
k-=1
if __name__ == "__main__":
array1 = [2,4,6,8]
m = len(array1)
array2 = [1,3,5,7]
n = len(array2)
array1 [m:] = array2[:n]
print array1
merge_sort(array1,array2,m,n)
print array1
