Merge Sort

Merge sort เป็นวิธีการเรียงลำดับที่อาศัยการทำงานแบบ divide and conquer (เหมือน quick sort แต่มีหลักการทำงานต่างกัน) โดยแบ่งอาเรย์ออกเป็นสองชุด ปริมาณเท่า ๆ กัน นำชุดซ้ายไปเรียงลำดับ แล้วก็นำชุดขวาไปเรียงลำดับ แล้วจึงนำข้อมูลทั้งสองชุดมาผสาน (merge) กันจนได้ข้อมูลทั้งหมดที่เรียงลำดับ

การทดลองข้างล่างนี้ป้อนข้อมูลเริ่มต้นให้กับ merge sort สามแบบ คือ ข้อมูลเรียงเรียบร้อยแล้ว ข้อมูลเรียงกลับลำดับ และ ข้อมูลสุ่ม ให้สังเกตว่า การเรียงลำดับข้อมูลที่เรียงลำดับแล้ว กับกรณีที่เรียงกลับลำดับ มีภาระการทำงานพอ ๆ กัน และเร็วกว่ากรณีข้อมูลสุ่ม

(อย่าลืมอ่านข้อแนะนำในการตีความผลการทดลอง)


สมชาย ประสิทธิ์จูตระกูล