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

 typedef struct s_node {
   int            data;
   struct s_node *next;
 } s_node_t, *node_t;
 node_t root = NULL;

void quit(char *msg)
{
  fprintf(stderr, "example: %s, sorry quitting.\n", msg);
  exit(1);
}

node_t new_node(int data, node_t next)
{
  node_t new = malloc(sizeof(s_node_t));
  if (NULL == new) quit("Out of memory");
  new->data = data;
  new->next = next;
  return new;
}

void insert_sort(int number)
{
  node_t *pp = &root;
  while (*pp && (*pp)->data < number)
    pp = &((*pp)->next);
  *pp = new_node(number, *pp);
}

void insert_sort_two(int number)
{
  node_t n;
  if (NULL == root || root->data >= number) {
    root = new_node(number, root);
  }
  else {
    n = root;
    while (NULL != n->next && n->next->data < number)
      n = n->next;
    n->next = new_node(number, n->next);
  }
}

void insert_sort_three(int number)
{
  node_t p, n;
  if (NULL == root || root->data >= number) {
    root = new_node(number, root);
  }
  else {
    n = (p = root)->next;
    while (NULL != n && n->data < number)
      n = (p = n)->next;
    p->next = new_node(number, n);
  }
}

int main(int argc, char **argv)
{
  node_t n;

  insert_sort_three(72);
  insert_sort_three(4); /* Smallest yet. */
  insert_sort_three(18);
  insert_sort_three(23);
  insert_sort_three(9);

  insert_sort_two(7);
  insert_sort_two(32);
  insert_sort_two(2); /* Smallest yet. */
  insert_sort_two(6);
  insert_sort_two(44);

  insert_sort(5);
  insert_sort(8);
  insert_sort(1); /* Smallest yet. */
  insert_sort(99);
  insert_sort(3);


  for (n = root; n; n = n->next) {
    if (n != root) printf(", ");
    printf("%d", n->data);
  }
  printf("\n");

  return 0;
}