Hướng dẫn Merge Sort trong Python

Sắp xếp dữ liệu là một trong những thao tác phổ biến nhất mà những người làm dữ liệu thực hiện hằng ngày. Nhiều khi chúng ta cần hiển thị dữ liệu theo một thứ tự nhất định để rút ra thông tin có ý nghĩa. May mắn là ngày nay chúng ta không phải làm thủ công nữa. Máy tính có thể làm điều đó cho chúng ta với hiệu năng vượt trội.

Có nhiều chiến lược để sắp xếp dữ liệu. Trong hướng dẫn này, chúng ta sẽ phân tích một trong những kỹ thuật sắp xếp hiệu quả nhất. Thuật toán “merge sort” sử dụng chiến lược chia để trị để sắp xếp một mảng chưa được sắp xếp bằng cách trước tiên chia nó thành các mảng nhỏ hơn, sau đó hợp nhất lại theo đúng thứ tự. 

Trong các phần tiếp theo, chúng ta sẽ thảo luận mọi chi tiết của thuật toán merge sort, cách triển khai trong Python và một số mẹo thực tiễn để triển khai trơn tru.

Merge Sort là gì?

Có rất nhiều thuật toán sắp xếp, nhưng khó tìm được thuật toán nào vượt trội hơn merge sort. Không có gì ngạc nhiên khi thuật toán này được dùng trong đủ loại ứng dụng thực tế, như sắp xếp cơ sở dữ liệu lớn hoặc tổ chức tệp trên máy tính thông thường.

Thuật toán dựa trên mô hình chia để trị, có thể chia thành ba phần:

• Chia: quá trình này chia bài toán thành các bài toán con nhỏ hơn. 
• Trị: các bài toán con được giải một cách đệ quy. 
• Kết hợp: kết hợp lời giải của các bài toán con để đạt được lời giải cuối cùng.

Chiến lược chia để trị

Hãy xem merge sort hoạt động thế nào. Giả sử chúng ta muốn sắp xếp các số sau bằng thuật toán merge sort. Thuật toán sẽ đệ quy chia dữ liệu thành hai phần và tiếp tục chia cho đến khi mỗi danh sách chỉ còn một phần tử. Sau đó, chúng ta kết hợp chúng lại bằng cách sắp xếp vào một danh sách khác.

Bài toán Merge Sort. Nguồn: DataCamp

Độ phức tạp thời gian và không gian của Merge Sort

Không thể biết trước thuật toán sắp xếp nào là tốt nhất cho một bài toán cụ thể. Có nhiều biến số cần cân nhắc ngoài bản thân thuật toán, bao gồm ngôn ngữ lập trình dùng để viết mã, phần cứng thực thi, và những đặc thù của dữ liệu cần sắp xếp. 

Dù không thể dự đoán chính xác thời gian chạy của một thuật toán sắp xếp, chúng ta vẫn có thể so sánh hiệu năng của các thuật toán khác nhau bằng cách phân tích độ phức tạp thời gian và không gian.

Độ phức tạp thời gian của merge sort

Như đã giải thích trong hướng dẫn riêng về Ký hiệu Big O và Độ phức tạp thời gian, mục tiêu của phân tích độ phức tạp thời gian không phải để dự đoán chính xác thời gian chạy, mà là đánh giá mức độ hiệu quả bằng cách phân tích thời gian chạy thay đổi thế nào khi lượng dữ liệu đầu vào tăng.

Phân tích độ phức tạp thời gian được viết bằng ký hiệu Big O, một ký hiệu toán học mô tả tốc độ tăng hoặc giảm của một hàm. Merge sort có độ phức tạp theo log-tuyến tính hay tuyến tính-log, ký hiệu là O(N log(N)), trong đó N là số phần tử của danh sách. Chữ 'O' là viết tắt của 'order' (bậc) tăng trưởng. 

Trong phân tích độ phức tạp thời gian, độ phức tạp tuyến tính-log có hành vi xấp xỉ giống tuyến tính, tức thời gian thực thi sẽ tỷ lệ thuận với lượng dữ liệu. Do đó, nếu lượng dữ liệu tăng gấp đôi, thời gian thuật toán xử lý dữ liệu cũng sẽ gần như tăng gấp đôi, tức số lần chia và hợp nhất sẽ tăng gấp đôi.

Vì độ phức tạp thời gian của merge sort có xu hướng tuyến tính theo dữ liệu đầu vào, độ phức tạp của nó giữ nguyên cho các trường hợp tốt nhất, trung bình và xấu nhất. Điều đó có nghĩa là, bất kể thứ tự đầu vào ra sao, thuật toán luôn thực hiện cùng số bước để hoàn thành.

Độ phức tạp không gian của merge sort

Cuối cùng, bên cạnh thời gian cần để hoàn thành tác vụ, một khía cạnh quan trọng khác khi phân tích độ phức tạp là ước lượng lượng bộ nhớ thuật toán cần khi bài toán lớn dần. 

Điều này được đề cập qua các khái niệm độ phức tạp không gian và không gian phụ trợ. Không gian phụ trợ là phần bộ nhớ bổ sung hay tạm thời mà thuật toán sử dụng, còn độ phức tạp không gian là tổng bộ nhớ thuật toán chiếm dụng so với kích thước đầu vào. Nói cách khác, độ phức tạp không gian bao gồm cả không gian phụ trợ và không gian cho đầu vào.

Merge sort có độ phức tạp không gian O(N). Lý do là nó dùng một mảng phụ có kích thước N để hợp nhất hai nửa đã được sắp. Mảng phụ trợ này lưu kết quả đã hợp nhất, và mảng đầu vào sẽ bị ghi đè bằng kết quả đã sắp xếp.

Triển khai Merge Sort trong Python

Hãy triển khai thuật toán merge sort trong Python. Có nhiều cách viết mã cho thuật toán; tuy nhiên, chúng ta sẽ bám theo cách dựa trên đệ quy, vốn dễ hiểu hơn và cần ít dòng mã hơn so với các phương án dựa trên vòng lặp.

Hiểu đệ quy trong merge sort

Nếu bạn còn mới với chủ đề này, trong lập trình, đệ quy xảy ra khi một hàm gọi lại chính nó. Bạn có thể xem Hướng dẫn Hiểu về Hàm Đệ quy trong Python để tìm hiểu đầy đủ về những hàm mạnh mẽ này.

Để triển khai merge sort, trước hết ta xác định trường hợp cơ sở: nếu danh sách chỉ có một phần tử, nó đã được sắp xếp, vì vậy trả về ngay. Ngược lại, ta chia danh sách thành hai nửa, left_half và right_half, và gọi đệ quy merge_sort() trên từng nửa. Quá trình này tiếp tục cho đến khi mọi danh sách con chỉ còn một phần tử.

Khi đã có các danh sách con đã sắp xếp, ta bắt đầu quá trình hợp nhất. Để làm điều này, ta khởi tạo ba biến chỉ số: i để theo dõi vị trí trong left_half, j cho right_half, và k cho danh sách hợp nhất cuối cùng. Sau đó, ta so sánh các phần tử từ cả hai nửa. Nếu phần tử hiện tại trong left_half nhỏ hơn, ta đặt nó vào my_list[k] và tăng i. Ngược lại, ta lấy phần tử từ right_half, đặt vào my_list[k], và tăng j. Sau mỗi lần so sánh, ta tăng k để chuyển sang vị trí tiếp theo trong danh sách cuối.

Quá trình này tiếp tục cho đến khi so sánh xong toàn bộ phần tử ở một trong hai nửa. Nếu còn phần tử nào trong left_half hoặc right_half, ta chép thẳng chúng vào danh sách cuối, đảm bảo không bỏ sót dữ liệu. Vì merge sort hoạt động đệ quy, quá trình hợp nhất này được thực thi ở mọi cấp của đệ quy cho đến khi toàn bộ danh sách được sắp xếp.

Triển khai bằng Python

Bên dưới là đoạn mã sử dụng danh sách chưa sắp xếp trong sơ đồ trước làm ví dụ:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]Được hỗ trợ bởi

Merge Sort so với các thuật toán sắp xếp khác

Merge sort là một thuật toán sắp xếp khá nhanh, đặc biệt phù hợp với các cơ sở dữ liệu lớn, và thường được dùng làm chuẩn đối chiếu cho các thuật toán khác. Tuy nhiên, với danh sách ngắn hơn, hiệu năng của nó thường kém hơn một số thuật toán sắp xếp khác.

Trong bảng dưới đây, bạn có thể xem so sánh giữa merge sort và các thuật toán sắp xếp phổ biến khác.

Ứng dụng thực tiễn của Merge Sort

Merge sort có hiệu năng cao khi sắp xếp các danh sách lớn, nhưng hiệu quả giảm khi làm việc với danh sách nhỏ. Tương tự, nó có xu hướng kém hiệu quả trong các tình huống đầu vào đã có một mức độ trật tự nhất định, vì merge sort sẽ thực hiện cùng số bước bất kể thứ tự của danh sách.

Một trường hợp sử dụng rất phù hợp cho merge sort là danh sách liên kết (linked list). Linked list là một cấu trúc dữ liệu gồm các nút được liên kết tuyến tính với nhau. Mỗi nút chứa dữ liệu và liên kết đến nút tiếp theo.

Merge sort được ưa chuộng cho linked list vì chỉ đòi hỏi truy cập tuần tự vào dữ liệu, rất phù hợp với bản chất của linked list. Ngoài ra, merge sort là thuật toán sắp xếp ổn định (tức là giữ nguyên thứ tự tương đối của các phần tử bằng nhau trong kết quả), điều này rất quan trọng để duy trì thứ tự trong linked list.

Lỗi thường gặp và cách khắc phục

Thuật toán merge sort khá trực quan, và không có quá nhiều chỗ để cải tiến mã. Tuy vậy, bạn có thể tăng độ tinh vi cho chiến lược sắp xếp bằng cách tính đến kích thước dữ liệu đầu vào. 

Chúng ta đã xác định rằng merge sort hoạt động tốt hơn với tập dữ liệu lớn. Với tập dữ liệu nhỏ, các thuật toán có độ phức tạp O(N^2) như insertion sort có thể hoạt động tốt hơn. Trong trường hợp này, bạn chỉ cần đặt một ngưỡng kích thước mà dưới ngưỡng đó bạn sẽ chọn insertion sort thay cho merge sort.

Ngoài ra, một ý tưởng đáng thử là song song hóa. Các bước của merge sort có thể dễ dàng song song hóa nếu có đủ năng lực tính toán, từ đó rút ngắn thời gian hoàn thành. Đọc hướng dẫn CPU vs GPU để tìm hiểu thêm về tính toán song song. 

Kết luận

Merge sort là một trong những thuật toán sắp xếp hiệu quả và phổ biến nhất, nhưng còn rất nhiều điều để học trong thế giới thuật toán rộng lớn và luôn phát triển. Nếu bạn quan tâm đến khía cạnh kỹ thuật của thuật toán, cách chúng hoạt động, cùng độ phức tạp, ưu và nhược điểm liên quan, các tài nguyên từ DataCamp sau có thể giúp bạn tiếp tục học tập:

• Khóa học Nhập môn Cấu trúc Dữ liệu và Thuật toán 
• Lộ trình Kỹ năng Lập trình Python
• Lộ trình Kỹ năng Nền tảng Dữ liệu với Python
• Khóa học Python Trung cấp
• Lộ trình Nghề nghiệp Chuyên viên Phân tích Dữ liệu với Python 
• Ký hiệu Big O và Độ phức tạp thời gian