Thuat Toan MergeSort

Ý tưởng:
Merge sort chia danh sách dữ liệu  cần được sắp xếp thành hai nữa bằng nhau, và đặt chúng vào các vùng chứa  dữ liệu riêng biệt (list, array,…). Mỗi mảng dữ liệu được sắp xếp một  cách đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được  sắp xếp cuối cùng. Giống như hầu hết các phương pháp sắp xếp đệ quy,  Merge sort có độ phức tạp là O(n log n).
Cách triển khai cơ bản của Merge sort là dùng ba mảng dữ liệu – mỗi mảng  để chứa mổi nữa của tập dữ liệu cần sắp xếp và một mảng chứa danh sách  được sắp xếp cuối cùng. Thuật toán được giới thiệu sau đây trộn các mảng  lại thành một, vì vậy chỉ sử dụng hai mảng cho toàn bộ quá trình xử lý.  Hiện nay cũng tồn tại phiên bản không đệ quy của Merge sort, nhưng  chúng không thu được bất kì một cải tiến tốc độ nào so với phiên bản đệ  quy qua thử nghiệm trên hầu hết các kiến trúc xử lý.
Merge sort thì nhanh hơn một ít so với Heap sort với các tập dữ liệu  lớn, nhưng nó đòi hỏi 2 lần bộ nhớ so với Heap sort vì vậy nó không được  ưa chuộng trong việc triển khai ứng dụng dù cho mục đích là gì – Quick  sort là lựa chọn tốt hơn cho thời gian và Heap sort thì lại là lựa chọn  tốt hơn với các tập dữ liệu rất lớn.
Giống như Quick sort, Merge sort là phương pháp dựa trên đệ quy, điều  này khiến nó sẽ là lựa chọn tồi với các ứng dụng chạy trên máy tính bị  giới hạn về bộ nhớ.
Thuật giải:

- Ta xem dãy cần sắp xếp có N phần tử là N đoạn và mỗi đoạn đã được sắp xếp là dãy tăng dần rồi (Tất nhiên vì chỉ mỗi đoạn chỉ có 1 phần tử).
- Sau đó ta trộn 2 đoạn liên tiếp nhau để tạo thành các đoạn có độ dài bằng 2 sao cho mỗi đoạn đã được sắp xếp tăng dần.
- Và tiếp tục cứ trộn 2 đoạn liên tiếp, ta sẽ được những đoạn có độ dài lớn hơn và đồng thời số đoạn trong dãy cũng sẽ ít đi... và cho tới khi chỉ còn lại 1 đoạn duy nhất là dãy đã được sắp xếp tăng dần.
Ví dụ:  Cho dãy : 38 , 27 , 43 , 3 , 9 , 82  , 10

Ví dụ:   Cho dãy: 6 , 5 ,  3 , 1 , 8 ,  7 ,  2 ,  4

Cài dặt:

void merge(int a[],int k1,int k2,int k3)
{
int i,j,z,t[100];
i=k1;
j=k2;
z=k1;
// Tron phan tu
// So sanh cac phan tu de dua vao day T
while((i<k2)&&(j<=k3))
{
if (a[i]<=a[j]) //***
{
t[z]=a[i];
i++;
}
else
{
t[z]=a[j];
j++;
}
z++;
}
// Gan cac phan tu con lai cua day (k1->k2-1) vao day T (neu con)
if(i>=k2)
while (z<=k3)
{
t[z]=a[j];
j++;
z++;
}
// Gan cac phan tu con lai cua day (k2->k3) vao day T (neu con)
if (j>k3)
while (z<=k3)
{
t[z]=a[i];
i++;
z++;
}
// Sao chep day T vao day A
for(z=k1;z<=k3;z++)
a[z]=t[z];
}