#include <stdio.h>

int max(int a, int b) {
    return ((a > b) ? a : b);
}

int min(int a, int b) {
    return ((a < b) ? a : b);
}

int fgetsize(FILE *f) {
    int pos = ftell(f);
    fseek(f, 0, SEEK_END);
    int size = ftell(f);
    fseek(f, pos, SEEK_SET);
    return size;
}

int main(void) {
    FILE *f, *f1, *f2, *flast;

    f1 = fopen("f1.txt", "w");
    fclose(f1);
    f2 = fopen("f2.txt", "w");
    fclose(f2);

    do {
        f = fopen("f.txt", "r");
        f1 = fopen("f1.txt", "w");
        f2 = fopen("f2.txt", "w");
        int x, last;
        //Распределение
        while (true) {
            int ret = fscanf(f, "%d", &x);
            if (ret != EOF) {
                if (fgetsize(f1) == 0) {
                    fprintf(f1, "%d ", x);
                    last = x;
                }
                else {
                    if (last <= x) {
                        fprintf(f1, "%d ", x);
                        last = x;
                    }
                    else {
                        fprintf(f2, "%d ", x);
                    }
                }
            }
            else {
                break;
            }
        }

        fclose(f);
        fclose(f1);
        fclose(f2);

        f = fopen("f.txt", "w");
        f1 = fopen("f1.txt", "r");
        f2 = fopen("f2.txt", "r");
        int a, b;
        //Слияние
        while (true) {
            int ret1 = fscanf(f1, "%d", &a);
            int ret2 = fscanf(f2, "%d", &b);
            if (ret1 != EOF && ret2 != EOF) {
                fprintf(f, "%d %d ", min(a, b), max(a, b));
            }
            else {
                if (ret1 == EOF && ret2 != EOF) {
                    fprintf(f, "%d ", b);
                    while (fscanf(f2, "%d", &b) != EOF) {
                        fprintf(f, "%d ", b);
                    }
                }
                else if (ret1 != EOF && ret2 == EOF) {
                    fprintf(f, "%d ", a);
                    while (fscanf(f1, "%d", &a) != EOF) {
                        fprintf(f, "%d ", a);
                    }
                }
                break;
            }
        }
        if (fgetsize(f2) == 0)
            break;

        fclose(f);
        fclose(f1);
        fclose(f2);
    } while(true);

    fclose(f);
    fclose(f1);
    fclose(f2);

    return 0;

}