/* Ineffective, non-generic, recursive Quicksort in C */

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

struct cons { int head; struct cons *tail; };
#define CONS(h, t) (&(struct cons){ h, t})

static struct cons *last(struct cons *l)
{
     if (l == NULL) return l;

     struct cons *p = NULL;
     while (p = l, (l = l->tail) != NULL);
     return p;
}

static struct cons *append(struct cons *l1, struct cons *l2)
{
     struct cons *end = last(l1);
     if (end == NULL) l1 = l2;
     else end->tail = l2;
     return l1;
}

static void partition(struct cons *list, struct cons *pivot, struct cons **ge, struct cons **lt)
{
     struct cons copy;
     do {
          copy = *list;
          struct cons **l = list->head < pivot->head ? ge : lt;
          list->tail = *l;
          *l = list;
     } while ((list = copy.tail) != NULL);
}

static struct cons *sort(struct cons *list)
{
     if (list == NULL || list->tail == NULL) return list;
     struct cons *pivot = list, *lt = NULL, *ge = NULL;
     partition(list->tail, pivot, &lt, &ge);
     pivot->tail = NULL;
     return append(sort(lt), append(pivot, sort(ge)));
}

static void print(struct cons *list)
{
     while (printf("%d, ", list->head), (list = list->tail));
     puts("");
}

int main()
{
     struct cons *l = CONS(10, CONS(32, CONS(2, CONS(3, CONS(32, NULL)))));
     print(l);
     l = sort(l);
     print(l);
     return 0;
}