データ構造のマージアルゴリズム

マージアルゴリズムは、2つの並べ替えられたリストを1つのリストにマージするために使用されます。このアルゴリズムはさまざまな場合に使用されます。マージソートを実行する場合は、ソーターリストをより大きなリストにマージする必要があります。

アプローチは簡単です。 2つのリストを取ります。2つのポインタがあります。最初のものは最初のリストの要素を指し、2番目のものは2番目のリストの要素を指します。それらの値に基づいて、これら2つのリストのいずれかから小さい要素が取得され、対応するリストのポインターが増加します。この操作は、1つのリストがなくなるまで実行されます。その後、最後にマージされたリストの最後に残りのリストを追加します。

より良いアイデアを得るためにイラストを見てみましょう。

アルゴリズム

マージ（配列、左、中央、右）-

Begin
   nLeft := m - left+1
   nRight := right – m
   define arrays leftArr and rightArr of size nLeft and nRight respectively
   for i := 0 to nLeft do
      leftArr[i] := array[left +1]
   done
   for j := 0 to nRight do
      rightArr[j] := array[middle + j +1]
   done
   i := 0, j := 0, k := left
   while i < nLeft AND j < nRight do
      if leftArr[i] <= rightArr[j] then
         array[k] = leftArr[i]
         i := i+1
      else
         array[k] = rightArr[j]
         j := j+1
         k := k+1
      done
   while i < nLeft do
      array[k] := leftArr[i]
      i := i+1
      k := k+1
   done
   while j < nRight do
      array[k] := rightArr[j]
      j := j+1
      k := k+1
   done
End