データ構造-マージソートアルゴリズム
マージソートは、分割統治法に基づくソート手法です。最悪の場合の時間計算量はΟ（nlog n）であり、これは最も尊敬されているアルゴリズムの1つです。
マージソートは、最初に配列を等しい半分に分割し、次にそれらをソートされた方法で結合します。
マージソートはどのように機能しますか？
マージソートを理解するために、ソートされていない配列を次のように取ります。
マージソートは、アトミック値が達成されない限り、最初に配列全体を繰り返し等しい半分に分割することを知っています。ここでは、8つのアイテムの配列がサイズ4の2つの配列に分割されていることがわかります。
これにより、オリジナルのアイテムの表示順序は変更されません。次に、これら2つの配列を半分に分割します。
これらの配列をさらに分割すると、これ以上分割できない原子値が得られます。
今、私たちはそれらが分解されたのとまったく同じ方法でそれらを組み合わせます。これらのリストに記載されているカラーコードに注意してください。
最初に各リストの要素を比較し、次にそれらをソートされた方法で別のリストに結合します。14と33がソートされた位置にあることがわかります。27と10を比較し、2つの値のターゲットリストで最初に10を入力し、次に27を配置します。19と35の順序を変更しますが、42と44は順番に配置されます。
結合フェーズの次の反復では、2つのデータ値のリストを比較し、それらをすべてソートされた順序で配置して、見つかったデータ値のリストにマージします。
最終的なマージ後、リストは次のようになります-
ここで、マージソートのプログラミングの側面をいくつか学ぶ必要があります。
アルゴリズム
マージソートは、リストを分割できなくなるまで、リストを均等に分割し続けます。定義上、リスト内の要素が1つしかない場合は、並べ替えられます。次に、マージソートは、新しいリストもソートされたまま、小さいソート済みリストを結合します。
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.擬似コード
ここで、マージソート関数の擬似コードを確認します。私たちのアルゴリズムが指摘しているように、2つの主要な機能-分割とマージ。
マージソートは再帰で機能し、実装も同じように表示されます。
procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedureCプログラミング言語でのマージソートの実装については、ここをクリックしてください。