Thuật toán sắp xếp trộn (Merge sort)

Thuật toán sắp xếp trộn (Merge sort) là một thuật toán sắp xếp đệ quy được sử dụng rộng rãi trong các ứng dụng thực tế. Cách thức hoạt động của thuật toán này như sau:

1. Chia danh sách cần sắp xếp thành hai phần bằng nhau.
2. Sắp xếp hai phần đó bằng cách sử dụng thuật toán sắp xếp trộn (Merge Sort).
3. Trộn hai phần đã sắp xếp lại với nhau để tạo thành danh sách đã sắp xếp.

Thuật toán sắp xếp trộn được chia làm hai phần chính: quá trình chia đôi danh sách và quá trình trộn hai danh sách đã sắp xếp. Quá trình chia đôi danh sách được thực hiện đệ quy cho đến khi danh sách chỉ còn một phần tử.

Độ phức tạp của thuật toán sắp xếp trộn (Merge sort) là O(n log n), tốc độ nhanh hơn so với các thuật toán sắp xếp cơ bản khác.

Dưới đây là đoạn code Python mẫu để sắp xếp một danh sách sử dụng thuật toán sắp xếp trộn:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr

Ví dụ: Cho danh sách [64, 25, 12, 22, 11]. Sử dụng thuật toán sắp xếp trộn, ta có kết quả sau khi sắp xếp là [11, 12, 22, 25, 64].

arr = [64, 25, 12, 22, 11]
sorted_arr = merge_sort(arr)
print(sorted_arr) # Kết quả là [11, 12, 22, 25, 64]