MÔ PHỎNG THUẬT TOÁN MERGE SORT

Merge Sort – Chia để trị

Ý tưởng: Chia mảng thành hai nửa, sắp xếp từng nửa, rồi trộn lại.

Chia → Sắp → Trộn

Độ sâu: 0

Kích thước: 8

Nhấn "Bắt đầu" để xem mô ph��ng thuật toán Merge Sort

📝 Lịch sử các bước thực hiện

Chưa có bước nào được thực hiện. Nhấn "Bắt đầu" để bắt đầu.

🐍 Code Python - Giải thuật Merge Sort

def merge_sort(arr):
    # Trường hợp cơ sở: mảng có 0 hoặc 1 phần tử
    if len(arr) <= 1:
        return arr
    
    # Chia mảng thành hai nửa
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Đệ quy sắp xếp từng nửa
    left = merge_sort(left)
    right = merge_sort(right)
    
    # Trộn hai mảng đã sắp xếp
    return merge(left, right)


def merge(left, right):
    # Tạo mảng kết quả
    result = []
    i = j = 0
    
    # So sánh và trộn hai mảng
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Thêm các phần tử còn lại (nếu có)
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result


# Ví dụ sử dụng
arr = [42, 17, 33, 5, 88, 21, 9, 60]
print("Mảng ban đầu:", arr)

sorted_arr = merge_sort(arr)
print("Mảng đã sắp xếp:", sorted_arr)

# Kết quả: [5, 9, 17, 21, 33, 42, 60, 88]

Độ phức tạp: O(n log n)

Ổn định, hiệu quả cho mảng lớn.