//归并排序
void mergeSort(int *arr, int num) {
int* a = arr;
int* b = (int*) malloc(num * sizeof(int));
int seg, start;
for (seg = 1; seg < num; seg += seg) {
for (start = 0; start < num; start += seg + seg) {
int low = start, mid = min(start + seg, num), high = min(start + seg + seg, num);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2){
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1){
b[k++] = a[start1++];
}
while (start2 < end2){
b[k++] = a[start2++];
}
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < num; i++)
b[i] = a[i];
b = a;
}
free(b);
} |