Thuật toán Merge dùng để hợp nhất hai danh sách đã sắp xếp thành một danh sách. Dùng trong Merge Sort để hợp nhất các danh sách con đã sắp xếp thành danh sách lớn hơn.
Cách tiếp cận đơn giản: hai danh sách, hai con trỏ. Con trỏ 1 trỏ phần tử danh sách 1, con trỏ 2 trỏ danh sách 2. So sánh giá trị, lấy phần tử nhỏ hơn, tăng con trỏ danh sách đó. Lặp cho đến khi một danh sách hết. Sau đó nối phần còn lại của danh sách kia vào cuối.
Minh họa:
Thuật toán
Merge(array, left, middle, right) −
Begin
nLeft := m - left + 1
nRight := right - m
define arrays leftArr, rightArr size nLeft, nRight
for i := 0 to nLeft do
leftArr[i] := array[left + i]
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