数据结构二路插入排序c语言代码

以下是二路插入排序的C语言代码示例：

// 二路插入排序
void TwoWayInsertSort(int r[], int n) {
    int i, j, low, high, mid;
    int temp[n+1];
    temp[0] = r[0]; // 哨兵
    low = 0;
    high = 0;
    for (i = 1; i <= n; i++) {
        if (r[i] < temp[low]) { // 插入到前半部分
            low = (low - 1 + n) % n;
            temp[low] = r[i];
        } else if (r[i] >= temp[high]) { // 插入到后半部分
            high = (high + 1) % n;
            temp[high] = r[i];
        } else { // 插入到中间部分
            mid = (low + 1) % n;
            while (r[i] >= temp[mid]) {
                low = mid;
                mid = (mid + 1) % n;
            }
            high = (high + 1) % n;
            for (j = high; j != mid; j = (j - 1 + n) % n) {
                temp[j] = temp[(j - 1 + n) % n];
            }
            temp[mid] = r[i];
        }
    }
    for (i = 1; i <= n; i++) {
        r[i] = temp[(low + i) % n];
    }
}