Merge sort เป็นการเรียงลำดับแบบ หาร-แล-พิชิต เสถียร ที่ทำงานในเวลา O(n log n) ที่รับประกัน โดยแบ่งอาร์เรย์ออกครึ่งหนึ่ง เรียงลำดับแต่ละครึ่งแบบเรียกซ้ำ จากนั้นรวมสองครึ่งที่เรียงลำดับแล้วเข้าด้วยกัน
องค์ประกอบเดียวจะถูกเรียงลำดับแล้ว (กรณีฐาน) การรวมสองรายการที่เรียงลำดับเป็นแบบเชิงเส้น และเราทำการรวม log n ระดับ
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
เหมาะสมเมื่อคุณต้องการ เสถียรภาพ หรือ O(n log n) ที่รับประกัน และสำหรับ รายการที่เชื่อมโยง และ การเรียงลำดับภายนอก ของไฟล์ขนาดใหญ่ หน่วยความจำ O(n) พิเศษเป็นข้อเสียหลัก
Merge sort รับประกัน O(n log n) ไม่ว่าอินพุตจะเป็นอย่างไร ซึ่งแตกต่างจากกรณีที่แย่ที่สุด O(n²) ของ quicksort
ความเสถียรของมันรักษาลำดับสัมพัทธ์ของคีย์เดียวกัน ซึ่งเป็นสิ่งสำคัญสำหรับการเรียงลำดับแบบหลายคีย์
ขั้นตอนการรวมเป็นพื้นฐานที่สามารถนำกลับมาใช้ได้ และโครงสร้างหาร-แล-พิชิตเป็นเทมเพลตที่คุณจะนำกลับมาใช้ได้ทุกที่