void jsw_selection ( int a[], int n )
{
  while ( --n > 0 ) {
    int i, max = n;

    for ( i = 0; i < n; i++ ) {
      if ( a[i] >= a[max] )
        max = i;
    }

    if ( max != n ) {
      int save = a[max];

      for ( i = max; i < n; i++ )
        a[i] = a[i + 1];

      a[n] = save;
    }
  }
}

void jsw_insertion ( int a[], int n )
{
  int i;

  for ( i = 1; i < n; i++ ) {
    int j, save = a[i];

    for ( j = i; j >= 1 && a[j - 1] > save; j-- )
      a[j] = a[j - 1];

    a[j] = save;
  }
}

void jsw_insertion ( struct jsw_list *list )
{
  struct jsw_node result = {0};
  struct jsw_node *i, *step, *next;

  for ( step = list->head; step != NULL; step = next ) {
    next = step->next;

    for ( i = &result; i->next != NULL; i = i->next ) {
      if ( i->next->data > step->data )
        break;
    }

    step->next = i->next;
    i->next = step;
  }

  list->head = result.next;
}

void jsw_shellsort ( int a[], int n )
{
  int i, h = 1;

  while ( h <= n  9 )
    h = 3 * h + 1;

  while ( h > 0 ) {
    for ( i = h; i < n; i++ ) {
      int j, save = a[i];

      for ( j = i; j >= h && a[j - h] > save; j -= h )
        a[j] = a[j - h];

      a[j] = save;
    }

    h = 3;
  }
}

/* Median of three, obviously */
int jsw_partition ( int a[], int first, int last )
{
  int pivot, mid = ( first + last ) / 2;

  /* Largest of two */
  pivot = a[first] > a[mid] ? first : mid;

  /* Smallest of remaining */
  if ( a[pivot] > a[last] )
    pivot = last;

  jsw_swap ( &a[pivot], &a[first] );
  pivot = first;

  while ( first < last ) {
    if ( a[first] <= a[last] )
      jsw_swap ( &a[pivot++], &a[first] );

    ++first;
  }

  jsw_swap ( &a[pivot], &a[last] );

  return pivot;
}

void jsw_quicksort_r ( int a[], int first, int last )
{
  /* Use another method on almost-sorted array */
  if ( last - first > THRESHOLD ) {
    int pivot;

    /* Avoid work if the subarray is sorted */
    if ( is_sorted ( a, first, last ) )
      return;
    
    pivot = jsw_partition ( a, first, last );
    jsw_quicksort_r ( a, first, pivot - 1 );
    jsw_quicksort_r ( a, pivot + 1, last );
  }
}

void jsw_quicksort ( int a[], int n )
{
  jsw_quicksort_r ( a, 0, n - 1 );

  /* Finalize the sort */
  jsw_insertion ( a, n );
}

void jsw_introsort_r ( int a[], int first, int last, int depth )
{
  while ( last - first > THRESHOLD ) {
    if ( depth == 0 )
      jsw_heapsort ( &a[first], last - first + 1 );
    else {
      int pivot;

      if ( is_sorted ( a, first, last ) )
        return;
    
      pivot = jsw_partition ( a, first, last );
      jsw_introsort_r ( a, pivot + 1, last, depth - 1 );
      last = pivot - 1;
    }
  }
}

void jsw_introsort ( int a[], int n )
{
  jsw_introsort_r ( a, 0, n - 1, (int)( 2 * log ( n ) ) );
  jsw_insertion ( a, n );
}

/* 
  Remove a node from a list and
  push it onto a tail pointer
*/
#define split_push(head,tail,item) do { \
  struct jsw_node *save = item->next; \
  item->next = NULL; \
  if ( tail == NULL ) \
    head = tail = item; \
  else { \
    tail->next = item; \
    tail = tail->next; \
  } \
  item = save; \
}while ( 0 );

struct jsw_node *jsw_merge ( struct jsw_node *a, 
  struct jsw_node *q[2] )
{
  int dir = q[0]->data > q[1]->data;
  struct jsw_node *save = a = q[dir];

  /* Intended assignment */
  while ( q[dir] = q[dir]->next ) {
    dir = q[0]->data > q[1]->data;

    if ( q[dir]->data < a->data 
      && a->data < q[!dir]->data )
    {
      dir = !dir;
    }

    a->next = q[dir];
    a = a->next;
  }

  dir = q[0] == NULL;

  while ( q[dir] != NULL ) {
    a->next = q[dir];
    q[dir] = q[dir]->next;
    a = a->next;
  }

  return save;
}

void jsw_mergesort ( struct jsw_list *list )
{
  struct jsw_node *q[2] = {0};
  struct jsw_node *a = list->head;

  for ( ; ; ) {
    struct jsw_node *end[2] = {0};
    int half = 0;

    split_push ( q[0], end[0], a );

    while ( a != NULL ) {
      if ( a->data < end[half]->data )
        half = !half;
      split_push ( q[half], end[half], a );
    }

    if ( q[0] == NULL || q[1] == NULL )
      break;

    a = jsw_merge ( a, q );
  }

  list->head = q[q[0] == NULL];
}

#define RANGE ( ( 1U << CHAR_BIT ) + 1 )
#define digit(x,i) ( (x) >> ( (i) * CHAR_BIT ) & UCHAR_MAX )

void jsw_radix_pass ( int a[], int aux[], int n, int radix )
{
  int i;
  int count[RANGE] = {0};

  for ( i = 0; i < n; i++ )
    ++count[digit ( a[i], radix ) + 1];

  for ( i = 1; i < RANGE; i++ )
    count[i] += count[i - 1];

  for ( i = 0; i < n; i++ )
    aux[count[digit ( a[i], radix )]++] = a[i];

  for ( i = 0; i < n; i++ )
    a[i] = aux[i];
}

void jsw_radixsort ( int a[], int n )
{
  int i;
  int *aux = malloc ( n * sizeof *aux );

  for ( i = 0; i < sizeof *a; i++ )
    jsw_radix_pass ( a, aux, n, i );

  free ( aux );
}

/* Extract ith MSD byte */
#define digit(x,i) ( (x)[i] )
#define bin(x) ( first + count[x] )

void jsw_radix_pass ( char *a[], char *aux[],
  int count[], int first, int last, int radix )
{
  int i;

  for ( i = first; i < last; i++ )
    ++count[digit ( a[i], radix ) + 1];

  for ( i = 1; i < UCHAR_MAX; i++ )
    count[i] += count[i - 1];

  for ( i = first; i < last; i++ )
    aux[count[digit ( a[i], radix )]++] = a[i];

  for ( i = first; i < last; i++ )
    a[i] = aux[i - first];
}

void jsw_radixsort_r ( char *a[], char *aux[],
  int first, int last, int radix )
{
  if ( radix <= UCHAR_MAX && last - first > THRESHOLD ) {
    int count[UCHAR_MAX + 1] = {0};
    int i;

    jsw_radix_pass ( a, aux, count, first, last, radix );

    for ( i = 0; i < UCHAR_MAX - 1; i++ ) {
      int left = bin ( i );
      int right = bin ( i + 1 ) - 1;
      jsw_radixsort_r ( a, aux, left, right, radix + 1 );
    }
  }
}

void jsw_radixsort ( char *a[], int n )
{
  char **aux = malloc ( ( n + 1 ) * sizeof *aux );

  jsw_radixsort_r ( a, aux, 0, n, 0 );
  jsw_insertion ( a, n );

  free ( aux );
}