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

→‎การวิเคราะห์: แก้ไขให้หัวข้อสื่อความหมายดีขึ้น "การวิเคราะห์" เป็น "เชิงวิเคราะห์"
(แก้คำผิด)
(→‎การวิเคราะห์: แก้ไขให้หัวข้อสื่อความหมายดีขึ้น "การวิเคราะห์" เป็น "เชิงวิเคราะห์")
</source>
 
==การเชิงวิเคราะห์==
[[ไฟล์: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 Theorem]] ในการวิเคราะห์สมการนี้จะได้ผลลัพทธ์เป็น O(''n'' log ''n'') ดังที่ได้กล่าวไว้
ผู้ใช้นิรนาม