/* Shuffle sort a.k.a. "cocktail sort" */

state =
{
  ulong flag;
  ulong rq_greater_or_lesser;
};

cmp = ((ptr, ptr) byte); 
swp = ((pptr -&w, pptr -&w) .);

sort (ptr -&w array[], int length, cmp compare, SORT_* order_by = SORT_ASC)
{
  swap (pptr -&w first, pptr -&w second)
  {
    *first = *second = *first;
  }

  state st = {
               flag : 1,
               rq_greater_or_lesser : (order_by == SORT_ASC) ? 1 : 0
             };

  sort (array, &st, length, compare, swap);
}

sort _ (ptr -&w array[], p_state -&w st, int length, cmp compare, swp swap)
{
  int begin = 0; 
  int end = (length - 1) - 1;

  while (st->flag)
  {
    left_to_right (array, st, begin - 1, end), { st->flag = 0; begin ++ } : st->flag;
    right_to_left (array, st, begin - 1, end), { st->flag = 0; end --   } : st->flag;
  }
}

/* Walking up the array.
   This function will move the greatest element 
   to the right bound of the array */

left_to_right sort (ptr -&w array[], p_state -&w st, int begin, int end, cmp compare, swp swap)
{
  for (i = begin, i < end, i ++)
  {
    swap_two (array, st, i, compare, swap);
  }
}  

/* Walking down the array.
   This function will move the lowest element 
   to the left bound of the array */

right_to_left sort (ptr -&w array[], p_state -&w st, int begin, int end, cmp compare, swp swap)
{
  for (i = end - 1, i >= begin, i --)
  {
    swap_two (array, st, i, compare, swap);
  }
}

/* Swapping two neighbors */

swap_two left_to_right, right_to_left (ptr -&w array[], p_state -&w st, int first, cmp compare, swp swap)
{
  second = first + 1;

  if (compare (array[first], array[second]) == st->rq_greater_or_lesser)
  {
    swap (&array[first], &array[second]); st->flag = 1;
  }
}

