算法学习笔记：归并排序与逆序数计算优化

// 归并函数，合并两个已排序的子数组
int* merge(int* left, int left_len, int* right, int right_len) {
int* result = (int*)malloc(sizeof(int) * (left_len + right_len));
int l = 0, r = 0, k = 0;
while (l if (left[l] > right[r]) {
// 记录逆序数
count += left_len - l;
result[k++] = right[r++];
} else {
result[k++] = left[l++];
}
}
while (l result[k++] = left[l++];
}
while (r result[k++] = right[r++];
}
return result;
}

// 归并排序主函数
int* merge_sort(int* array, int array_len) {
if (array_len == 1) return array; // 单个元素直接返回
int mid = array_len / 2;
int* left = merge_sort(array, mid);
int* right = merge_sort(array + mid, array_len - mid);
int* result = merge(left, mid, right, array_len - mid);
return result;
}

// 改进后的归并排序，使用临时数组T来存储中间结果
void merge_sort(int* array, int start, int end, int* temp) {
if (end - start <= 1) return; // 只有一个元素或为空时直接返回
int mid = start + (end - start) / 2;
merge_sort(array, start, mid, temp); // 递归排序左半部分
merge_sort(array, mid, end, temp); // 递归排序右半部分
int l = start, r = mid, i = start;
while (l if (r >= end || (l temp[i++] = array[l++];
} else {
temp[i++] = array[r++];
// 如果需要计算逆序数，在这里累加
count += mid - l;
}
}
for (int i = start; i array[i] = temp[i]; // 将临时数组的结果复制回原数组
}
}