sort.c

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

typedef struct node {
    int i;
    struct node *next;
} List;

List *cons(int i, List *l) {
    List *n = malloc(sizeof(List));
    n->i = i;
    n->next = l;
    return n;
}

void printl(List *l) {
    if (l == NULL) {
        printf("\n");
        return;
    }
    printf("%d ", l->i);
    printl(l->next);
}

List *biggerthan(List *l, int x) {
    if (l == NULL) {
        return NULL;
    }
    if (l->i > x) {
        return cons(l->i, biggerthan(l->next, x));
    }
    return biggerthan(l->next, x);
}

List *smallerthan(List *l, int x) {
    if (l == NULL) {
        return NULL;
    }
    if (l->i < x) {
        return cons(l->i, smallerthan(l->next, x));
    }
    return smallerthan(l->next, x);
}

List *eqto(List *l, int x) {
    if (l == NULL) {
        return NULL;
    }
    if (l->i == x) {
        return cons(l->i, eqto(l->next, x));
    }
    return eqto(l->next, x);
}

List *merge(List *l1, List *l2) {
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    if (l1->i < l2->i) {
        return cons(l1->i, merge(l1->next, l2));
    }
    return cons(l2->i, merge(l1, l2->next));
}

List *append(List *l1, List *l2) {
    if (l1 == NULL) {
        if (l2 == NULL) {
            return NULL;
        }
        return append(l2, NULL);;
    }
    return cons(l1->i, append(l1->next, l2));
}

List *sort(List *l) {
    if (l == NULL) {
        return l;
    }
    return merge(
            sort(smallerthan(l, l->i)),
            append(eqto(l, l->i), sort(biggerthan(l, l->i)))
            );
}

int main() {
    List *l = NULL;
    l = cons(3, l);
    l = cons(1, l);
    l = cons(4, l);
    l = cons(1, l);
    l = cons(5, l);
    l = cons(9, l);
    l = cons(2, l);
    l = cons(6, l);
    l = cons(5, l);
    l = cons(3, l);

    printl(l);
    printf("Sorted: \n");
    List *sorted = sort(l);
    printl(sorted);
}