อัลกอริทึม Python

Merge Sort ใน Python

แบ่งข้อมูลแบบ recursive แล้วรวม list ย่อยที่เรียงแล้ว

Merge Sort ใน Python คืออะไร?

แบ่งข้อมูลแบบ recursive แล้วรวม list ย่อยที่เรียงแล้ว

เรียงข้อมูลด้วยแนวคิด divide and conquer

ควรใช้เมื่อใด?

  • ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
  • สังเกตแต่ละขั้นตอนและกรณีขอบ
  • เปรียบเทียบเวลาและหน่วยความจำ

ภาพจำลอง Merge Sort ใน Python

O(n log n)

กด เล่น หรือ ทีละขั้น เพื่อดูการเปรียบเทียบและการย้ายข้อมูลแต่ละขั้น

โค้ดตัวอย่าง

รันโค้ด →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

ผลลัพธ์ที่คาดหวัง

[3, 9, 10, 27, 38, 43, 82]

หลักการทำงาน

รับประกันเวลา O(n log n) และใช้หน่วยความจำเพิ่ม O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัด

ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น

  1. ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นตอน
  3. เปรียบเทียบประสิทธิภาพกับวิธีอื่น
รันใน Python IDE →