package bench;
class HeapSortAlgorithm
    extends SortAlgorithm
{
    public HeapSortAlgorithm()
    {
        super("HeapSortAlgorithm");
    }

    private final void swap(int i, int j)
    {
      int T;

      T = a[i];
      a[i] = a[j];
      a[j] = T;
    }

    public final void performTest()
    {
      int length = a.length;
      int i, j, k;

      for (i = length/2; i > 0; i--)
      {
        j = i;
        while (true)
        {
          k = j*2;
          if (k > length) break;

          if ( (k < length) && (a[k-1] < a[k]) ) k++;

          if (a[j-1] < a[k-1]) swap (j-1, k-1); else break;
          j = k;
        }
      }

      i = length;
      do
      {
        j = 1;
        swap (j-1, i-1);
        i --;
        while (true)
        {
          k = j*2;
          if (k > i) break;

          if ( (k < i) && (a[k-1] < a[k]) ) k++;
          swap (j-1, k-1);
          j = k;
        }
        while (true)
        {
          k = j / 2;
          if ((k > 0) && (a[k-1] < a[j-1]) )
          {
            swap (j-1, k-1);
            j = k;
          }
          else
            break;
        }
      }while (i > 0);
    }

}
