데이터 구조의 병합 알고리즘

병합 알고리즘은 두 개의 정렬된 목록을 하나의 목록으로 병합하는 데 사용됩니다. 이 알고리즘은 다양한 경우에 사용됩니다. 병합 정렬을 수행하려면 분류기 목록을 더 큰 목록으로 병합해야 합니다.

접근 방식은 간단합니다. 우리는 두 개의 목록을 가져옵니다. 두 개의 포인터가 있을 것입니다. 첫 번째 항목은 첫 번째 목록의 요소를 가리키고 두 번째 항목은 두 번째 목록의 요소를 가리킵니다. 값에 따라 이 두 목록 중 하나에서 더 작은 요소를 가져온 다음 해당 목록의 포인터를 늘립니다. 이 작업은 하나의 목록이 소진될 때까지 수행됩니다. 그 후 최종 병합 목록의 끝에 나머지 목록을 추가합니다.

더 나은 아이디어를 얻기 위해 그림을 보자.

알고리즘

병합(배열, 왼쪽, 가운데, 오른쪽) -

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