Merge Algorithms ในโครงสร้างข้อมูล

Merge Algorithm

ใช้รวม 2 Sorted Lists ให้กลายเป็น 1 List ใช้ใน Merge Sort เพื่อรวม Sorted Lists ให้ใหญ่ขึ้น

แนวทาง

มี 2 Pointers ชี้ที่ List 1 และ List 2 เปรียบเทียบค่า นำค่าน้อยกว่าเข้า Merged List เพิ่ม Pointer ของ List นั้น ทำซ้ำจน List ใด List หนึ่งหมด แล้วต่อ List ที่เหลือท้าย Merged List

ภาพประกอบ

อัลกอริทึม

Merge(array, left, middle, right) −
Begin
    nLeft := m - left + 1
    nRight := right - m
    define arrays leftArr and rightArr of size nLeft and 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