Merge sort là gì một thuật toán sắp xếp dựa trên kỹ thuật chia và chinh phục. độ phức tạp thời gian của sắp xếp hợp nhất là O (n log n). Đầu tiên, thuật toán chia mảng thành các nửa bằng nhau và sau đó hợp nhất chúng theo một cách nhất định.
Sắp xếp hợp nhất lặp lại
Trong sắp xếp hợp nhất lặp đi lặp lại, chúng tôi sẽ chia các phần tử thành các nửa bằng nhau bằng cách sử dụng phương pháp đệ quy và sau đó hợp nhất chúng trở lại dưới dạng một mảng được sắp xếp bằng cách sử dụng phương pháp lặp lại.
Chương trình sắp xếp hợp nhất lặp lại
/ * Chương trình đệ quy C để sắp xếp hợp nhất * /
Ví dụ
#include<stdlib.h>
#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void iterativeMergeSort(int arr[], int l, int r) {
if (l < r){
int mid = l+(r-l)/2;
iterativeMergeSort(arr, l, mid);
iterativeMergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
}
}
int main(){
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("\t\t ITERATIVE MERGE SORT \n");
printf("Unsorted Array : \t");
for (int i=0; i < size; i++)
printf("%d ",arr[i]);
iterativeMergeSort(arr, 0, size - 1);
printf("\nSorted array : \t");
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
} Đầu ra
ITERATIVE MERGE SORT Unsorted Array : 12 11 13 5 6 7 Sorted array : 5 6 7 11 12 13