Pythonマージソート

マージソートは（英語：Merge sort、またはmergesort）、マージ操作で作成された効果的なソートアルゴリズムです。このアルゴリズムは、分割統治法（Divide and Conquer）の非常に典型的な応用です。

分割統治法：

分割：現在のシーケンスを再帰的に2つに均等に分割します。
統合：要素の順序を維持しながら、前のステップで取得したサブシーケンスを統合（マージ）します。

実例

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 

　# 一時配列を作成する
    L = [0] * (n1)
    R = [0] * (n2)

　 # データを一時配列arrays L[] およびR[]にコピーする 
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
 
   # 一時配列をarr [l..r]にマージする 
    i = 0     # 最初のサブ配列のインデックスを初期化する
    j = 0     # 2番目のサブ配列のインデックスを初期化する
    k = l     # マージされたサブ配列のインデックスを初期化する

  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
 
# L[] の要素をコピーする

    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
 
#R[] の要素をコピーする

    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
def mergeSort(arr,l,r): 
    if l < r: 
 
        m = int((l+(r-1))/2)

        mergeSort(arr, l, m) 
        mergeSort(arr, m+1, r) 
        merge(arr, l, m, r) 

arr = [12, 11, 13, 5, 6, 7] 
n = len(arr) 

print ("指定された配列") 
for i in range(n): 
    print ("%d" %arr[i]), 
  
mergeSort(arr,0,n-1) 
print ("\n\nソートされた配列") 
for i in range(n): 
    print ("%d" %arr[i]),

上記のコードを実行した結果は次のとおりです。

指定された配列
12
11
13
5
6
7

ソートされた配列
5
6
7
11
12
13