Sắp xếp trộn (Merge Sort) trong C

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Chương trình minh họa sắp xếp trộn (Merge Sort) trong C

Dưới đây là ví dụ minh họa cho cách thực hiện giải thuật sắp xếp trộn (Merge Sort) trong ngôn ngữ C.

#include 
#define max 10int a[10] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }   while(l1 <= mid)    
      b[i++] = a[l1++];   while(l2 <= high)   
      b[i++] = a[l2++];   for(i = low; i <= high; i++)
      a[i] = b[i];
}void sort(int low, int high) {
   int mid;
   
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   }else { 
      return;
   }   
}int main() { 
   int i;   printf("Danh sach truoc khi duoc sap xep\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);   sort(0, max);   printf("\nDanh sach sau khi duoc sap xep\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả: