Merge sort là một thuật toán sắp xếp theo divide-and-conquer, ổn định (stable), chạy với thời gian O(n log n) được đảm bảo. Nó chia mảng làm đôi, sắp xếp đệ quy mỗi nửa, rồi trộn hai nửa đã sắp xếp lại.
Một phần tử đơn lẻ thì đã được sắp xếp (base case). Việc trộn hai danh sách đã sắp xếp là tuyến tính, và chúng ta thực hiện log n tầng trộn.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sắp xếp nửa trái
right = merge_sort(arr[mid:]) # sắp xếp nửa phải
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= giữ cho thuật toán ổn định
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Lý tưởng khi bạn cần tính ổn định hoặc O(n log n) được đảm bảo, và cho linked list cũng như sắp xếp ngoại (external sorting) các tệp khổng lồ. Bộ nhớ phụ O(n) là nhược điểm chính của nó.
Merge sort đảm bảo O(n log n) bất kể đầu vào, không như trường hợp xấu nhất O(n²) của quicksort.
Tính ổn định của nó bảo toàn thứ tự tương đối của các khóa bằng nhau, điều quan trọng khi sắp xếp theo nhiều khóa.
Bước trộn là một nguyên thủy có thể tái sử dụng, và cấu trúc divide-and-conquer là một khuôn mẫu bạn sẽ tái sử dụng ở khắp nơi.