C语言实现归并排序（递归与非递归）

 归并，分而治之，当数组不可再分，借助额外数组空间进行排序，非递归实现是对递归的模拟

void _MergeSort(int* nums, int left, int right, int* temp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(nums, left, mid, temp);_MergeSort(nums, mid + 1, right, temp);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int dst = left;while (begin1 <= end1 && begin2 <= end2){if (nums[begin1] <= nums[begin2]){temp[dst++] = nums[begin1++];}else{temp[dst++] = nums[begin2++];}}while (begin1 <= end1){temp[dst++] = nums[begin1++];}while (begin2 <= end2){temp[dst++] = nums[begin2++];}memcpy(nums + left, temp + left, (right - left + 1) * sizeof(int));
}void MergeSort(int* nums, int numsSize)
{int* temp = (int*)malloc(sizeof(int) * numsSize);assert(temp != NULL);_MergeSort(nums, 0, numsSize - 1, temp);free(temp);
}

void MergeSortNonR(int* nums, int numsSize)
{int* temp = (int*)malloc(sizeof(int) * numsSize);assert(temp != NULL);for (int gap = 1; gap < numsSize; gap *= 2){for (int i = 0; i < numsSize; i += 2 * gap){int begin1 = i;int end1 = begin1 + gap - 1;int begin2 = end1 + 1;int end2 = begin2 + gap - 1;if (end1 >= numsSize){end1 = numsSize - 1;begin2 = numsSize;end2 = numsSize - 1;}else if (begin2 >= numsSize){begin2 = numsSize;end2 = numsSize - 1;}else if (end2 >= numsSize){end2 = numsSize - 1;}int dst = i;while (begin1 <= end1 && begin2 <= end2){if (nums[begin1] <= nums[begin2]){temp[dst++] = nums[begin1++];}else{temp[dst++] = nums[begin2++];}}while (begin1 <= end1){temp[dst++] = nums[begin1++];}while (begin2 <= end2){temp[dst++] = nums[begin2++];}}memcpy(nums, temp, numsSize * sizeof(int));}
}