[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Thuật toán sắp xếp Merge sort. (Sắp xếp hòa nhập, sắp xếp trộn)

1. Bubble sort. (Nổi bọt, nổi bong bóng)
2. Quick sort. (Sắp xếp nhanh)
3. Simple selection sort. (Sắp xếp chọn)
4. Thuật toán sắp xếp chèn
5. Heap sort. (Sắp xếp vun đống)
6. Simple insertion sort.(Sắp xếp chèn)
7.  Shell sort.
8. Thuật toán sắp xếp hòa nhập

1. Bài toán
Cho dãy X = {X1, X1, ..., Xn}, hãy sắp xếp dãy theo chiều không giảm.
2. Ý tưởng
- Giả sử dãy X[1],...,X[i],...,X[n] có hai đoạn đã được sắp xếp không giảm là X[1],...,X[i] và X[i+1],...,X[n], ta tiến hành tạo ra dãy mới bằng cách lần lượt lấy hai phần tử đầu tiên của mỗi đoạn và so sánh với nhau. Phần tử nào nhỏ hơn thì lấy ra dãy mới và bỏ nó ra khỏi đoạn đang xét. Cứ tiến hành như vậy cho tới khi một dãy bị vét hết (không còn phần tử nào). Lấy toàn bộ phần tử còn lại của đoạn không xét hết nối vào sau dãy đích. Như vậy dãy mới là một dãy đã được sắp xếp.
- Trong mọi trường hợp, có thể coi dãy gồm duy nhất 1 phần tử là đã được sắp xếp. Lợi dụng việc này, ta phân chia một dãy ra thành nhiều dãy con chỉ gồm một phần tử rồi lần lượt hòa nhập từng đôi một với nhau.

Thuật toán viết bằng C++ : 

Code:
// Thủ tục trộn gọi đệ quy
void MergeSort(int X[], int L, int R)
{
     int M;
     if (L<R){
     M=int((L+R)/2);
     MergeSort(X,L,M);
     MergeSort(X,M+1,R);
     Merge(X,L,M+1,R);
}
}

// Thủ tục trộn hai đoạn đã sắp xếp trong một dãy
void Merge(int a[], int k1, int k2, int k3)
{
     int i,j,k,t;
     int temp[];
     i=k1; j=k2; k=k3;
     while (i<k2) and (j<=k3)
    {
       if (a[i]<=a[j]){
       temmp[k]=a[i];
       i=i+1;
     }
else{
      temp[k]=a[j];
       j=j+1;
    }
k=k+1;
}
if (i>=k2)
for(t=j;t<=k3,t++)
      temp[k+t-j]=a[t];
else
for(t=i;t<=k2,t++)
     temp[k+t-i]=a[t];
for(k=k1;t<=k3,k++)
     a[k]=temp[k];
}