歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列;即先使每個子序列有序，再使子序列段間有序若將兩個有序表合并成一個有序表，稱為2-路歸并。

算法描述

• 把長度為?的輸入序列分成兩個長度為N / 2的子序列;
• 對這兩個子序列分別采用歸并排序;

• 將兩個排序好的子序列合并成一個最終的排序序列。

  
  
  歸并排序

代碼實現(xiàn)

# 歸并排序
#這是合并的函數(shù)
# 將序列L[first...mid]與序列L[mid+1...last]進行合并
def mergearray(L,first,mid,last,temp):
#對i,j,k分別進行賦值
    i,j,k = first,mid+1,0
#當左右兩邊都有數(shù)時進行比較，取較小的數(shù)
    while (i <= mid) and (j <= last):
        if L[i] <= L[j]:
            temp[k] = L[i]
            i = i+1
            k = k+1
        else:
            temp[k] = L[j]
            j = j+1
            k = k+1
#如果左邊序列還有數(shù)
    while (i <= mid):
        temp[k] = L[i]
        i = i+1
        k = k+1
#如果右邊序列還有數(shù)
    while (j <= last):
        temp[k] = L[j]
        j = j+1
        k = k+1
#將temp當中該段有序元素賦值給L待排序列使之部分有序
    for x in range(0,k):
        L[first+x] = temp[x]
# 這是分組的函數(shù)
def merge_sort(L,first,last,temp):
    if first < last:
        mid = (int)((first + last) / 2)
#使左邊序列有序
        merge_sort(L,first,mid,temp)
#使右邊序列有序
        merge_sort(L,mid+1,last,temp)
#將兩個有序序列合并
        mergearray(L,first,mid,last,temp)
# 歸并排序的函數(shù)
def merge_sort_array(L):
#聲明一個長度為len(L)的空列表
    temp = len(L)*[None]
#調(diào)用歸并排序
    merge_sort(L,0,len(L)-1,temp)

算法表現(xiàn)

歸并排序是一種穩(wěn)定的排序方法。和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因為始終都是O（nlogn）的時間復雜度代價是需要額外的內(nèi)存空間。