ผสานอัลกอริทึมในโครงสร้างข้อมูล

อัลกอริทึม Merge ใช้เพื่อรวมรายการที่เรียงลำดับสองรายการเป็นรายการเดียว อัลกอริทึมนี้ใช้ในกรณีต่างๆ หากเราต้องการทำการจัดเรียงแบบผสาน เราต้องรวมรายการตัวเรียงลำดับเป็นรายการขนาดใหญ่

วิธีการนั้นง่าย เราใช้สองรายการจะมีตัวชี้สองตัว อันแรกจะชี้ไปที่องค์ประกอบของรายการกำปั้น อันที่สองจะชี้ไปที่องค์ประกอบของรายการที่สอง ตามค่าของพวกเขา องค์ประกอบที่เล็กกว่าจะถูกนำมาจากหนึ่งในสองรายการนี้ จากนั้นเพิ่มตัวชี้ของรายการที่เกี่ยวข้องนั้น การดำเนินการนี้จะดำเนินการจนกว่ารายการหนึ่งจะหมด หลังจากนั้นให้เพิ่มรายการที่เหลือที่ส่วนท้ายของรายการที่รวมสุดท้าย

มาดูภาพประกอบกันดีกว่าครับ

อัลกอริทึม

ผสาน (อาร์เรย์ ซ้าย กลาง ขวา) −

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