Merge Sort: Thuật toán chia để trị (divide and conquer). Chia mảng làm đôi, sắp xếp đệ quy từng nửa, sau đó trộn (merge) hai nửa đã sắp xếp.
Logic Merge Sort
MergeSort(array, left, right):
if left < right:
mid = (left+right)/2
MergeSort(array, left, mid)
MergeSort(array, mid+1, right)
Merge(array, left, mid, right)
Logic Merge (trộn)
Merge(array, left, mid, right):
tạo mảng tạm tmp
i=left, j=mid+1, pos=0
while i<=mid && j<=right:
if array[i] < array[j] tmp[pos++] = array[i++]
else tmp[pos++] = array[j++]
copy phần còn lại của nửa trái/phải vào tmp
copy tmp về array[left..right]
Chương trình C hoàn chỉnh
#include <stdio.h>
void Merge(int *, int, int, int);
void MergeSort(int *array, int left, int right) {
int mid = (left+right)/2;
if(left < right) {
MergeSort(array, left, mid);
MergeSort(array, mid+1, right);
Merge(array, left, mid, right);
}
}
void Merge(int *array, int left, int mid, int right) {
int tmp[right-left+1];
int pos=0, i=left, j=mid+1;
while(i<=mid && j<=right) {
if(array[i] < array[j]) tmp[pos++] = array[i++];
else tmp[pos++] = array[j++];
}
while(i<=mid) tmp[pos++] = array[i++];
while(j<=right) tmp[pos++] = array[j++];
for(i=0;i
Kết quả
Kích thước: 10
Phần tử: 2 -10 34 -3 45 67 -89 34 23 67
Kết quả: -89 -10 -3 2 23 34 34 45 67 67