//
// Shell Sort implementation using Shell's increments
//
void
ShellSort (int A[], int N)
{
  int i, j, Increment, Tmp;

  for (Increment = N/2; Increment > 0; Increment /= 2)
   {
    for (i = Increment; i < N; i++)
      {
        Tmp = A[i];
        for (j = i; j >= Increment; j -=  Increment)
          if (Tmp < A[j - Increment])
            A[j] = A[j - Increment];
          else
            break;
        A[j] = Tmp;
      }
   }
}

#include <math.h>

//
// Shell Sort implementation using Shell's increments
//
void
ShellSortH (int A[], int N)
{
  int Increment, Tmp, j;

  for (Increment = (int) pow (2, (int)(log (N) / log (2))) / 2 - 1; 
       Increment > 0; Increment = ((Increment + 1) / 2) - 1) 
  {
    for (int i = Increment; i < N; i++)
      { 
        Tmp = A[i];
        for (j = i; j >= Increment; j -=  Increment)
          if (Tmp < A[j - Increment])
            A[j] = A[j - Increment];
          else
            break;
        A[j] = Tmp;
      }
  }
}