Giải thích Merge Sort trong Python

Merge sort (sắp xếp trộn) là một kỹ thuật sắp xếp. Đây là thuật toán sắp xếp hiệu quả với độ phức tạp thời gian O(n log n) trong đó n là độ dài mảng cần sắp xếp.

Merge sort tuân theo mô hình Divide and Conquer (Chia để trị). Nó liên tục chia mảng thành hai nửa bằng nhau. Sau đó bắt đầu sắp xếp các list chỉ có một phần tử và liên tục trộn các list đã sắp xếp để tạo thành list sắp xếp hoàn chỉnh.

Như vậy, ta được một mảng đã sắp xếp.

Ví dụ minh họa

Các hộp màu tím và mũi tên đen thể hiện việc tách list thành hai nửa.

Các hộp màu xanh lá và mũi tên đỏ thể hiện việc trộn hai list đã sắp xếp.

Triển khai Merge Sort

Chia list thành hai nửa khá dễ dàng và được thực hiện đệ quy cho đến khi chỉ còn một phần tử. Sau đó thủ tục trộn (merge) được thực hiện, đây chính là nơi áp dụng logic trộn hai list đã sắp xếp lại với nhau.

Ví dụ

Hàm merge nhận hai mảng đã sắp xếp cần trộn. Phần tử đầu tiên của a1 so sánh với phần tử đầu tiên của a2. Phần tử nhỏ hơn được thêm vào list c và con trỏ của mảng đó được tăng lên.

def merge(a1, a2):
    c = []
    x = 0
    y = 0
    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
    while x < len(a1):
        c.append(a1[x])
        x += 1
    while y < len(a2):
        c.append(a2[y])
        y += 1
    return c

def mergesort(array):
    if len(array) == 1:
        return array
    mid = len(array) // 2
    a1 = mergesort(array[:mid])
    a2 = mergesort(array[mid:])
    return merge(a1, a2)

array = [2, 3, 1, 5, 4, 6, 8, 10, 7, 9]
print(mergesort(array))

Kết quả

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