Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Merge Sort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết[khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…] về Merge Sort thông qua các phần sau.

Nội dung chính

Giống như QuickSort, Merge Sort là một thuật toán Chia và Chinh phục. Nó chia mảng đầu vào thành hai nửa, gọi chính nó cho hai nửa và sau đó hợp nhất hai nửa đã sắp xếp. Hàm merge [] được sử dụng để hợp nhất hai nửa. Hợp nhất [arr, l, m, r] là quá trình quan trọng giả định rằng arr [l..m] và arr [m + 1..r] được sắp xếp và hợp nhất hai mảng con đã sắp xếp thành một. Xem cách triển khai C sau để biết thêm chi tiết.

MergeSort [arr [], l, r]
Nếu r> l
Tìm điểm giữa để chia mảng thành hai nửa:
        Ở giữa m = [l + r] / 2
Hợp nhất cuộc gọi Sắp xếp cho nửa đầu:
         Gọi mergeSort[arr, l, m]
Hợp nhất cuộc gọi Sắp xếp cho nửa sau:
        Gọi mergeSort[arr, m + 1, r]
Hợp nhất hai nửa được sắp xếp ở bước 2 và 3:
         Gọi merge[arr, l, m, r]
`

Sơ đồ sau đây từ wikipedia cho thấy quy trình sắp xếp hợp nhất hoàn chỉnh cho một mảng ví dụ {38, 27, 43, 3, 9, 82, 10}. Nếu chúng ta xem xét kỹ hơn sơ đồ, chúng ta có thể thấy rằng mảng được chia đệ quy làm hai nửa cho đến khi kích thước trở thành 1\. Khi kích thước trở thành 1, các quá trình hợp nhất sẽ hoạt động và bắt đầu hợp nhất các mảng trở lại cho đến khi mảng hoàn chỉnh đã hợp nhất.

Hình ảnh minh hoạ

![][//cafedev.vn/wp-content/uploads/2020/10/cafedev_Merge-Sort-Tutorial.png] 

## 2\. Code ví dụ trên nhiều ngôn ngữ

C++

include

using namespace std; // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge[int arr[], int l, int m, int r] {

int n1 = m - l + 1; 
int n2 = r - m; 
// Create temp arrays  
int L[n1], R[n2]; 
// Copy data to temp arrays L[] and R[]  
for[int i = 0; i < n1; i++] 
    L[i] = arr[l + i]; 
for[int j = 0; j < n2; j++] 
    R[j] = arr[m + 1 + j]; 
// Merge the temp arrays back into arr[l..r] 
// Initial index of first subarray 
int i = 0;  
// Initial index of second subarray 
int j = 0;  
// Initial index of merged subarray 
int k = l; 
while [i < n1 && j < n2] 
{ 
    if [L[i]