ผลต่างระหว่างรุ่นของ "การเรียงลำดับแบบผสาน"

==การวิเคราะห์==
[[Image:merge sort algorithm diagram.svg|thumb|right|300px|ภาพแสดงการเรียงลำดับแถวลำดับ 7 ตัวด้วยวิธีการผสาน (แบบบนลงล่าง)]]
ในการเรียงลำดับข้อมูลทั้งสิ้น n ชุด ''การเรียงลำดับแบบผสาน'' มีประสิทธิภาพในกรณีดีที่สุด (โดยมิได้ใส่เงื่อนไขพิเศษ) กรณีเฉลี่ย และกรณีแย่สุด เท่ากันคือ O(''n'' log ''n'') โดยจะแสดงให้ดูดังนี้ สมมติให้เวลาที่ใช้ในการเรียงข้อมูล n ชุด แทนด้วย ''T''(''n'') เนื่องจาก ''การเรียงลำดับแบบผสาน'' มีสองขั้นตอนซึ่งโดย'''ขั้นแรก'''คือการแบ่งเป็นสองส่วนซึ่งสามารถทำได้ในเวลาคงที่แต่จะต้องเวียงบังเกิดเรียกตัวเองลงไปแก้ปัญหาที่เล็กลงครึ่งหนื่งสองปัญหา จะได้ว่าในส่วนแรกใช้เวลา 2''T''(''n''/2) และ'''ขั้นที่สอง'''ซึ่งเป็นการผสานข้อมูลสองชุดที่เล็กกว่า (ที่เรียงในตัวเองแล้ว) เป็นข้อมูลชุดใหญ่จะใช้เวลาอีก ''n'' ดังที่ได้แสดงให้ดูในตัวอย่างการอิมพลิเมนต์ด้านบน เมื่อรวมทั้งสองขั้นแล้วจะใช้เวลาทั้งสิ้น ''T''(''n'') = 2''T''(''n''/2) + ''n'' หากใช้ [[Master Theroem]] ในการวิเคราะห์สมการนี้จะได้ผลลัพทธ์เป็น O(''n'' log ''n'') ดังที่ได้กล่าวไว้
 
==อ้างอิง==
907

การแก้ไข