Giống như QuickSort , Merge Sort là một thuật toán Chia và Trị.
Bài Toán
Cần sắp xếp mảng A[1...n]. Thuật toán sắp xếp trộn được phát triển dựa trên chia để trị, bao gồm các thao tác sau:
- Chia (Divide):
- Chia dãy gồm n phần tử cần sắp xếp ra thành hai dãy, mỗi dãy có n/2 phần tử.
- Trị (Conquer):
- Sắp xếp mỗi dãy con một cách để quy sử dụng sắp xếp trộn.
- khi dãy chỉ còn một phần tử thì trả lại phần tử này.
- Tổ hợp (Combine):
- Trộn (Merge) hai dãy-con-đã-được-sắp-xếp để thu được dãy được sắp xếp gồm tất cả các phần tử của cả hai dãy con.
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 mẫu {38, 27, 43, 3, 9, 82, 10}.

Code hàm sắp xếp trộn
// 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] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of
// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}
Đăng nhận xét