Merge sort là gì? Thuật toán sắp xếp trộn Merge sort trong C/C++

Merge sort là phép toán được sử dụng khá phổ biến trong ngôn ngữ C/C++. Bài viết này sẽ giúp bạn hiểu rõ hơn về Merge sort để có thể vận dụng vào trong công việc nhé!

I. Sắp xếp trộn – Merge sort là gì?

1. Khái niệm

Merge sort hay còn được gọi là thuật toán sắp xếp trộn được hình thành và phát triển sự trên giải thuật chia để trị (Divide and conquer). Thuật toán này sẽ chia mang ra thành từng phần, sau đó tiến hành sắp xếp và trộn vào với nhau.

Sắp xếp trộn (Merge sort)

2. Ý tưởng

Thuật toán Merge sort chia mảng dữ liệu thành hai nửa (có thể bằng nhau hoặc chênh nhau 1 phần tử nếu mảng lẻ), sau đó lần lượt tiến hành sắp xếp trên từng phần một, sau đó kết hợp chúng lại với nhau thành một mảng hoàn chỉnh theo thứ tự sắp xếp.

3. Giải thuật

Bước 1: Tách đôi mảng ra làm hai phần bằng hoặc tương đương nhau và lưu vào 2 mảng tạm

Bước 2: Dùng đệ quy để chia nhỏ các phần đó ra cho đến khi không thể chia được nữa thì dừng lại

Bước 3: Sau khi chia nhỏ ra, bạn tiến hành sắp xếp các giá trị của hai phần lại và gộp lại thành một mảng chung

Bước 4: Kết hợp các giá trị con đã được sắp xếp với nhau thành một mảng mới.

Bước 5: Sau khi kết hợp lại, ta chỉ cần sắp xếp chúng để tiếp tục cho lần kết hợp kế tiếp.

Ví dụ thuật toán sắp xếp trộn (Merge sort)

II. Cách viết thuật toán sắp xếp trộn Merge sort

Gợi ý:

Sử dụng đệ qui để chia danh sách các phần tử thành hai nửa cho đến khi không chia thêm được nữa.
Tạo hai mảng tạm thời để chứa các phần tử sau khi chia, cùng với đó là hai mảng con L (trái) và R (phải).
Trường hợp chỉ có một phần tử thì xem như đã được sắp xếp.
Sau khi chia xong, sẽ gộp các phần tử ở mảng con R và L vào mảng chính.
Kết hợp các danh sách nhỏ đã sắp xếp với nhau thành một danh sách mới. Sau khi kết hợp tiến hành sắp xếp chúng để tiếp tục cho lần kết hợp kế tiếp.