根据 TAOCP 的算法流程图写的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdbool.h>

//
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

//
void pointer_swap(int** a, int** b) {
    int* temp = *a;
    *a = *b;
    *b = temp;
}


//
void print_data(int data[static 1], size_t len) {
    for (size_t i = 0; i < len; ++i) {
        printf("%d ", data[i]);
    }

    printf("\n");
}

//自然的两路合并排序
int natural_merge_sort(int data[static 1], size_t len) {
    int* src = data;
    int* dst = (int*)malloc(len*sizeof(int));
    if (!dst) return EXIT_FAILURE;

    int i = 0, j = len - 1;
    int k = 0, l = len - 1;
    int d = 1;

    bool is_next = false;

    for (;;) {
        if (i == j) {
            dst[k] = src[i];
            if (!is_next) {
                break;
            } else {
                i = 0, j = len - 1;
                k = 0, l = len - 1;
                d = 1;
                pointer_swap(&src, &dst);
                is_next = false;
            }
        }

        if (src[j] < src[i]) {
            dst[k] = src[j--];
            k += d;

            if (src[j] < src[j + 1]) {
                do {
                    dst[k] = src[i++];
                    k += d;
                } while (src[i - 1] <= src[i]);

                swap(&k, &l);
                d = -d;

                is_next = true;
            }
        } else {
            dst[k] = src[i++];
            k += d;
            if (src[i] < src[i - 1]) {
                do {
                    dst[k] = src[j--];
                    k += d;
                } while (src[j] >= src[j + 1]);

                swap(&k, &l);
                d = -d;

                is_next = true;
            }
        }
    }

    if (src == data) {
        memcpy(data, dst, len*sizeof(int));
        free(dst);
    } else {
        free(src);
    }

    return EXIT_SUCCESS;
}

int main(int argc, char* argv[argc + 1]) {
    int data[] = {503, 87, 512, 61, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703};
    natural_merge_sort(data, sizeof(data)/sizeof(int));
    print_data(data, sizeof(data)/sizeof(int));

    return EXIT_SUCCESS;
}