ในสาขาว ทยาการคอมพ วเตอร การเร ยงลำด บแบบผสาน อ งกฤษ Merge Sort เป นข นตอนว ธ ในการเร ยงลำด บท อาศ ยการเปร ยบเท ยบ และย

ในสาขาวิทยาการคอมพิวเตอร์ การเรียงลำดับแบบผสาน (อังกฤษ: Merge Sort) เป็นขั้นตอนวิธีในการเรียงลำดับที่อาศัยการเปรียบเทียบ และยังเป็นตัวอย่างขั้นตอนวิธีที่ใช้หลักการแบ่งแยกและเอาชนะทำให้ขั้นตอนวิธีนี้มีประสิทธิภาพ O(n log n) ในการอิมพลิเมนต์เพื่อการใช้งานจริง ๆ นั้นสามารถทำได้ทั้งแบบบนลงล่าง (Top-down) และแบบล่างขึ้นบน (Bottom-up) อนึ่งในการอิมพลิเมนต์โดยทั่วไปแล้วการเรียงแบบนี้จะไม่สูญเสียลำดับของข้อมูลที่มีค่าเท่ากัน นั่นคือเป็นการเรียงที่เสถียร การเรียงลำดับแบบผสาน ถูกเสนอขึ้นครั้งแรกโดยจอห์น ฟอน นอยมันน์ในปี ค.ศ. 1945

การเรียงลำดับแบบผสาน
ภาพตัวอย่างการเรียงลำดับแบบผสาน เร่มด้วยการแบ่งข้อมูลออกเป็นส่วนที่เล็กที่สุด แล้วเร่มผสานข้อมูลก้อนเล็ก ๆ เข้าด้วยกันกลายเป็นข้อมูลก้อนที่ใหญ่ขึ้น ในที่สุดข้อมูลทุกชิ้นจะเรียงลำดับอย่างสมบูรณ์
ประเภท	ขั้นตอนวิธีการเรียงลำดับ
โครงสร้างข้อมูล	แถวลำดับ (Array)
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	O(n log n)
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	O(n log n) โดยทั่วไป O(n) เมื่อใส่เงื่อนไขพิเศษ
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป	O(n log n)
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด	O(n) รวมทั้งแถวลำดับที่ช่วยในการเรียงอีกเท่าตัว

ขั้นตอนวิธี

ขั้นตอนวิธีอาศัยหลักการแบ่งแยกและเอาชนะและการเวียนบังเกิด โดยมีรายละเอียดดังนี้

(ขั้นตอนการแบ่ง) สมมติว่ามีข้อมูลอยู่ n ชุด
1. ถ้ามีข้อมูลแค่ 1 ชุด นั่นคือข้อมูลนั้นเรียงลำดับแล้ว
2. ถ้ามีข้อมูลมากกว่านั้น ให้แบ่งเป็นสองส่วน แล้วทำ
(ขั้นตอนเอาชนะ) เมื่อถึงขั้นตอนนี้จะได้ข้อมูลสองส่วน (โดยที่แต่ละส่วนเรียงในส่วนของตัวเองเรียบร้อยแล้ว) ทำการรวมข้อมูลทั้งสองส่วนนั้นให้เป็นข้อมูลก้อนเดียวที่ทั้งก้อนนั้นเรียงลำดับแล้ว

ตัวอย่างการอิมพลิเมนต์ด้วยรหัสเทียม ทำการเรียงลำดับด้วยการโยนลิสต์ข้อมูลไปที่ฟังก์ชัน MergeSort ผลลัพธ์ที่ออกจากฟังก์ชันนั้นคือข้อมูลที่เรียงลำดับแล้ว

MergeSort (array Assss) {  if (A.size == 0) return A  mid = A.size / 2  AA = MergeSort(A[0..mid])  BB = MergeSort(A[mid..A.size])  return MergeSort_Merge(AA, BB) } MergeSort_Merge (array A, array B) {  C = new array  aa = 0  bb = 0  while (aa < A.size and bb < B.size) {  if (A[aa] < B[bb]) {  C[] = A[aa++]  } else if (A[aa] > B[bb]) {  C[] = B[bb++]  } else {   aa += 1  bb += 1  }  }  while (aa < A.size) C[] = A[aa++]  while (bb < B.size) C[] = B[bb++]  return C }

เชิงวิเคราะห์

ภาพแสดงการเรียงลำดับแถวลำดับ 7 ตัวด้วยวิธีการผสาน (แบบบนลงล่าง)

ในการเรียงลำดับข้อมูลทั้งสิ้น n ชุด การเรียงลำดับแบบผสาน มีประสิทธิภาพในกรณีดีที่สุด (โดยมิได้ใส่เงื่อนไขพิเศษ) กรณีเฉลี่ย และกรณีแย่สุด เท่ากันคือ O(n log n) โดยจะแสดงให้ดูดังนี้ สมมติให้เวลาที่ใช้ในการเรียงข้อมูล n ชุด แทนด้วย T(n) เนื่องจาก การเรียงลำดับแบบผสาน มีสองขั้นตอนโดยขั้นแรกคือการแบ่งเป็นสองส่วนซึ่งสามารถทำได้ในเวลาคงที่แต่จะต้องเวียงบังเกิดเรียกตัวเองลงไปแก้ปัญหาที่เล็กลงครึ่งหนื่งสองปัญหา จะได้ว่าในส่วนแรกใช้เวลา 2T(n/2) และขั้นที่สองซึ่งเป็นการผสานข้อมูลสองชุดที่เล็กกว่า (ที่เรียงในตัวเองแล้ว) เป็นข้อมูลชุดใหญ่จะใช้เวลาอีก n ดังที่ได้แสดงให้ดูในตัวอย่างการอิมพลิเมนต์ด้านบน เมื่อรวมทั้งสองขั้นแล้วจะใช้เวลาทั้งสิ้น T(n) = 2T(n/2) + n หากใช้ ในการวิเคราะห์สมการนี้จะได้ผลลัพทธ์เป็น O(n log n) ดังที่ได้กล่าวไว้

อ้างอิง

Knuth (1998, p. 158)

บรรณานุกรม

Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. . Vol. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN . {{}}: |ref=harv ไม่ถูกต้อง ((help))

[1] Knuth (1998, p. 158)