//     compile with: R CMD SHLIB sort.c
// load into R with: dyn.load("sort.so")
// call from R with: .C("insertion", x = as.integer(sample(100, 10)),
//                       n = as.integer(10))

struct foo {
    int item;
    struct foo *next;
};

void insertion(int *x, int *nin)
{
    int n = nin[0];
    struct foo buffer[n];
    struct foo head;

    head.next = 0;

    for (int i = 0; i < n; i++) {
        struct foo *p = head.next;
        struct foo *psave = &head;
        for ( ; p != 0; psave = p, p = p->next) {
            if (x[i] > p->item) break;
        }
        buffer[i].item = x[i];
        buffer[i].next = p;
        psave->next = &buffer[i];
    }

    int i = 0;
    for (struct foo *p = head.next; p != 0; p = p->next, i++)
        x[i] = p->item;
}