Merge Sort ใน Python อธิบายพร้อมตัวอย่าง

Merge Sort คืออะไร?

Merge Sort เป็น Sorting Algorithm ที่มีประสิทธิภาพ Time Complexity O(n log n) โดยที่ n คือความยาวของ Array

Merge Sort ใช้หลัก Divide and Conquer (แบ่งและเอาชนะ):

1. แบ่ง Array ออกเป็น 2 ส่วนเท่าๆ กันซ้ำๆ จนเหลือ Element เดียว
2. รวม (Merge) สorted sub-arrays กลับมาเป็น Array ใหญ่ที่เรียงแล้ว

การทำงานแบบ Visual

สีม่วง/ลูกศรดำ: แบ่ง List เป็นครึ่ง
สีเขียว/ลูกศรแดง: รวม List ที่เรียงแล้ว

Implementation แบบ Recursive

def merge(a1, a2):
    """Merge two sorted arrays"""
    c = []
    x = y = 0
    
    # เปรียบเทียบ Element หน้าสุดของทั้งสอง Array
    while x < len(a1) and y < len(a2):
        if a1[x] < a2[y]:
            c.append(a1[x])
            x += 1
        else:
            c.append(a2[y])
            y += 1
    
    # เหลือ Element ใน a1
    while x < len(a1):
        c.append(a1[x])
        x += 1
    
    # เหลือ Element ใน a2
    while y < len(a2):
        c.append(a2[y])
        y += 1
    
    return c

def mergesort(array):
    # Base Case: Array มี 1 Element (เรียงแล้ว)
    if len(array) <= 1:
        return array
    
    # Divide
    mid = len(array) // 2
    a1 = mergesort(array[:mid])
    a2 = mergesort(array[mid:])
    
    # Conquer (Merge)
    return merge(a1, a2)

# ทดสอบ
array = [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
print("Original:", array)
print("Sorted:  ", mergesort(array))

ผลลัพธ์

Original: [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
Sorted:   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

คำอธิบายขั้นตอน

1. Base Case: ถ้า Array ความยาว 1 คืนค่าทันที (เรียงแล้ว)
2. Divide: หา Mid Point แบ่ง Array สองครึ่ง เรียก Recursive
3. Merge: รวม Two Sorted Arrays โดยเปรียบเทียบ Element หน้าสุด

Time & Space Complexity

Iterative Merge Sort (Bottom-Up)

def merge_sort_iterative(arr):
    n = len(arr)
    size = 1
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(left + size, n)
            right = min(left + 2 * size, n)
            if mid < right:
                arr[left:right] = merge(arr[left:mid], arr[mid:right])
        size *= 2
    return arr

Python Built-in: Timsort

Python ใช้ Timsort (Hybrid của Merge Sort + Insertion Sort) เป็น Built-in sorted() และ list.sort() ซึ่งมีประสิทธิภาพ O(n log n) และ Optimize สำหรับ Real-world Data

arr = [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
print(sorted(arr))      # New sorted list
arr.sort()              # In-place sort
print(arr)