การเรียงลำดับแบบผสาน
การเรียงลำดับแบบผสาน

การเรียงลำดับแบบผสาน

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

การเรียงลำดับแบบผสาน

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

ใกล้เคียง

การเรียนรู้ของเครื่อง การเร่งปฏิกิริยา การเรืองแสงของบรรยากาศ การเร็นเดอร์ การเรียนรู้เชิงลึก การเรียน การเรียกชื่อสารเคมีตามระบบไอยูแพ็ก การเรียงลำดับแบบฟอง การเรียกยานพาหนะคืนของโตโยต้า พ.ศ. 2552−2553 การเร่งโดยอาศัยแอนติบอดี