为何arrayone与arraytwo排序输出不一致？如何修复？

我编写了如下C语言代码，实现基于分段有序数组的自定义排序函数MySort：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int FindMid(int array[], int n) {
  int i;
  int m = 0;
  for (i = 0; i < n; i++) {
    if (i < n - 1 && array[i] > array[i + 1])
      m = i + 1;
  }
  return m;
}

void MySort(int array[], int n) {

  int i = 0;
  int l = 0;
  int t = FindMid(array, n);
  int m = t;
  int k = 0;
  int *temp = (int *)malloc(sizeof(int) * n * 2);

  for (i = 0; i < n; i++) {
    temp[i] = 0;
  }

  while (l < m && m < n) {
    if (array[l] <= array[m]) {
      temp[k++] = array[l++];
    } else {
      temp[k++] = array[m++];
    }
  }

  while (l < t) {
    temp[k++] = array[l++];
  }
  while (m < n) {
    temp[k++] = array[m++];
  }

  for (i = 0; i < n; i++) {
    array[i] = temp[i];
  }

  free(temp);
}

void print_ary(int *pa, int n) {
  int i;

  for (i = 0; i < n; i++) {
    printf("%d ", pa[i]);
  }
  printf("\n");
}

int main(void) {
  int arrayone[13] = {1, 6, 9, 16, 21, 2, 5, 11, 19, 25, 30, 33, 40};
  int arraytwo[13] = {1, 6, 9, 16, 21, 25, 30, 33, 40, 2, 5, 11, 19};
  int a = 13;
  MySort(arrayone, a);
  print_ary(arrayone, a);
  MySort(arraytwo, a);
  print_ary(arraytwo, a);

  return 0;
}

预期对arrayone和arraytwo排序后输出一致：

1 2 5 6 9 11 16 19 21 25 30 33 40
1 2 5 6 9 11 16 19 21 25 30 33 40

但实际输出不同：

1 2 5 6 9 11 16 19 21 2 5 11 19
1 2 5 6 9 11 16 19 21 25 30 33 40

我怀疑问题出在while(m<n){temp[k++]=array[m++]}语句，尝试将其替换为以下代码后结果仍无改善：

for (i = 0; i < n; i++) {
  if (temp[k - 1] < array[i]) {
    while (k < n) {
      temp[k++] = array[k++];
    }
  }
}

请问该如何修复这个问题？

问题根源 #

FindMid函数逻辑错误：它会遍历整个数组，每次遇到array[i] > array[i+1]就更新m为i+1。对于arrayone这种存在多段有序分段的数组（前5个元素有序、中间4个有序、最后4个有序），FindMid最终返回的是最后一个分段的起始位置（索引9），而非第一个分段结束后的起始点（索引5）。这导致归并逻辑只处理了前一段（0_{8）和最后一段（9}12），漏掉了中间的分段（5~8），所以排序后中间段元素被遗留到末尾。

修复方案 #

1. 修正FindMid函数

让它找到第一个逆序对后立即返回对应的分段起始位置，不再继续遍历更新：

int FindMid(int array[], int n) {
  int i;
  for (i = 0; i < n - 1; i++) {
    if (array[i] > array[i + 1])
      return i + 1; // 找到第一个逆序对直接返回
  }
  return 0; // 数组完全有序时返回0
}

2. 优化MySort函数

• 增加数组已完全有序的判断，直接返回避免无效计算
• 调整归并循环的判断条件，确保覆盖两个完整的有序分段
• 缩减临时数组的空间（只需n个元素即可）

修改后的MySort：

void MySort(int array[], int n) {
  int i = 0;
  int l = 0;
  int t = FindMid(array, n);
  
  // 数组已完全有序，无需处理
  if (t == 0) return;
  
  int m = t;
  int k = 0;
  int *temp = (int *)malloc(sizeof(int) * n); // 仅需n个元素空间

  while (l < t && m < n) {
    if (array[l] <= array[m]) {
      temp[k++] = array[l++];
    } else {
      temp[k++] = array[m++];
    }
  }

  // 处理前一段剩余元素
  while (l < t) {
    temp[k++] = array[l++];
  }
  // 处理后一段剩余元素
  while (m < n) {
    temp[k++] = array[m++];
  }

  for (i = 0; i < n; i++) {
    array[i] = temp[i];
  }

  free(temp);
}

效果验证 #

修改后，arrayone和arraytwo都能输出预期的正确排序结果。

内容的提问来源于stack exchange，提问作者kookoo