function [ indx, i, j ] = sort_heap_external ( n, indx, isgn )

%% SORT_HEAP_EXTERNAL externally sorts a list of items into ascending order.
%
%  Discussion:
%
%    The actual list of data is not passed to the routine.  Hence this
%    routine may be used to sort integers, reals, numbers, names,
%    dates, shoe sizes, and so on.  After each call, the routine asks
%    the user to compare or interchange two items, until a special
%    return value signals that the sorting is completed.
%
%  Modified:
%
%    05 February 2004
%
%  Reference:
%
%    A Nijenhuis and H Wilf,
%    Combinatorial Algorithms,
%    Academic Press, 1978, second edition,
%    ISBN 0-12-519260-6.
%
%  Parameters:
%
%    Input, integer N, the number of items to be sorted.
%
%    Input, integer INDX, the main communication signal.
%    The user must set INDX to 0 before the first call.
%    Thereafter, the user should set the input value of INDX
%    to the output value from the previous call.
%
%    Input, integer ISGN, results of comparison of elements I and J.
%    (Used only when the previous call returned INDX less than 0).
%    ISGN <= 0 means I is less than or equal to J;
%    0 <= ISGN means I is greater than or equal to J.
%
%    Output, integer INDX, the main communication signal.
%    If INDX is
%
%      greater than 0, the user should:
%      * interchange items I and J;
%      * call again.
%
%      less than 0, the user should:
%      * compare items I and J;
%      * set ISGN = -1 if I < J, ISGN = +1 if J < I;
%      * call again.
%
%      equal to 0, the sorting is done.
%
%    Output, integer I, J, the indices of two items.
%    On return with INDX positive, elements I and J should be interchanged.
%    On return with INDX negative, elements I and J should be compared, and
%    the result reported in ISGN on the next call.
%
  global SORT_HEAP_EXTERNAL_i;
  global SORT_HEAP_EXTERNAL_j;
  global SORT_HEAP_EXTERNAL_k;
  global SORT_HEAP_EXTERNAL_k1;
  global SORT_HEAP_EXTERNAL_n1;
%
%  INDX = 0: This is the first call.
%
  if ( indx == 0 )
      
    SORT_HEAP_EXTERNAL_i = -1;
    SORT_HEAP_EXTERNAL_j = -1;
    SORT_HEAP_EXTERNAL_k = floor ( n / 2 );
    SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_k;
    SORT_HEAP_EXTERNAL_n1 = n;
%
%  INDX < 0: The user is returning the results of a comparison.
%
  elseif ( indx < 0 )

    if ( indx == -2 )

      if ( isgn < 0 )
        SORT_HEAP_EXTERNAL_i = SORT_HEAP_EXTERNAL_i + 1;
      end

      SORT_HEAP_EXTERNAL_j = SORT_HEAP_EXTERNAL_k1;
      SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_i;
      indx = -1;
      i = SORT_HEAP_EXTERNAL_i;
      j = SORT_HEAP_EXTERNAL_j;
      return;
    end

    if ( 0 < isgn )
      indx = 2;
      i = SORT_HEAP_EXTERNAL_i;
      j = SORT_HEAP_EXTERNAL_j;
      return;
    end

    if ( SORT_HEAP_EXTERNAL_k <= 1 )

      if ( SORT_HEAP_EXTERNAL_n1 == 1 )
        indx = 0;
        i = 0;
        j = 0;
      else
        SORT_HEAP_EXTERNAL_i = SORT_HEAP_EXTERNAL_n1;
        SORT_HEAP_EXTERNAL_n1 = SORT_HEAP_EXTERNAL_n1 - 1;
        SORT_HEAP_EXTERNAL_j = 1;
        indx = 1;
        i = SORT_HEAP_EXTERNAL_i;
        j = SORT_HEAP_EXTERNAL_j;
      end

      return;

    end

    SORT_HEAP_EXTERNAL_k = SORT_HEAP_EXTERNAL_k - 1;
    SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_k;
%
%  0 < INDX, the user was asked to make an interchange.
%
  elseif ( indx == 1 )

    SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_k;

  end

  while ( 1 )

    SORT_HEAP_EXTERNAL_i = 2 * SORT_HEAP_EXTERNAL_k1;

    if ( SORT_HEAP_EXTERNAL_i == SORT_HEAP_EXTERNAL_n1 )
      SORT_HEAP_EXTERNAL_j = SORT_HEAP_EXTERNAL_k1;
      SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_i;
      indx = -1;
      i = SORT_HEAP_EXTERNAL_i;
      j = SORT_HEAP_EXTERNAL_j;
      return;
    elseif ( SORT_HEAP_EXTERNAL_i <= SORT_HEAP_EXTERNAL_n1 )
      SORT_HEAP_EXTERNAL_j = SORT_HEAP_EXTERNAL_i + 1;
      indx = -2;
      i = SORT_HEAP_EXTERNAL_i;
      j = SORT_HEAP_EXTERNAL_j;
      return;
    end

    if ( SORT_HEAP_EXTERNAL_k <= 1 )
      break;
    end

    SORT_HEAP_EXTERNAL_k = SORT_HEAP_EXTERNAL_k - 1;
    SORT_HEAP_EXTERNAL_k1 = SORT_HEAP_EXTERNAL_k;

  end

  if ( SORT_HEAP_EXTERNAL_n1 == 1 )
    indx = 0;
    i = 0;
    j = 0;
  else
    SORT_HEAP_EXTERNAL_i = SORT_HEAP_EXTERNAL_n1;
    SORT_HEAP_EXTERNAL_n1 = SORT_HEAP_EXTERNAL_n1 - 1;
    SORT_HEAP_EXTERNAL_j = 1;
    indx = 1;
    i = SORT_HEAP_EXTERNAL_i;
    j = SORT_HEAP_EXTERNAL_j;
  end