function [ indx, i, j ] = sort_heap_external ( n, indx, isgn )
%*****************************************************************************80
%
%% 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.
%
% Licensing:
%
% This code is distributed under the GNU LGPL license.
%
% Modified:
%
% 12 February 2010
%
% Author:
%
% Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf.
% MATLAB version by John Burkardt
%
% Reference:
%
% Albert Nijenhuis, Herbert Wilf.
% Combinatorial Algorithms,
% Academic Press, 1978, second edition,
% ISBN 0-12-519260-6.
%
% Input:
%
% integer N, the number of items to be sorted.
%
% 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.
%
% 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.
%
% 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.
%
persistent i_save;
persistent j_save;
persistent k;
persistent k1;
persistent n1;
if ( isempty ( i_save ) )
i_save = -1;
end
if ( isempty ( j_save ) )
j_save = -1;
end
%
% INDX = 0: This is the first call.
%
if ( indx == 0 )
k = floor ( n / 2 );
k1 = k;
n1 = n;
%
% INDX < 0: The user is returning the results of a comparison.
%
elseif ( indx < 0 )
if ( indx == -2 )
if ( isgn < 0 )
i_save = i_save + 1;
end
j_save = k1;
k1 = i_save;
indx = -1;
i = i_save;
j = j_save;
return;
end
if ( 0 < isgn )
indx = 2;
i = i_save;
j = j_save;
return;
end
if ( k <= 1 )
if ( n1 == 1 )
i_save = 0;
j_save = 0;
indx = 0;
else
i_save = n1;
n1 = n1 - 1;
j_save = 1;
indx = 1;
end
i = i_save;
j = j_save;
return;
end
k = k - 1;
k1 = k;
%
% 0 < INDX, the user was asked to make an interchange.
%
elseif ( indx == 1 )
k1 = k;
end
while ( true )
i_save = 2 * k1;
if ( i_save == n1 )
j_save = k1;
k1 = i_save;
indx = -1;
i = i_save;
j = j_save;
return;
elseif ( i_save <= n1 )
j_save = i_save + 1;
indx = -2;
i = i_save;
j = j_save;
return;
end
if ( k <= 1 )
break;
end
k = k - 1;
k1 = k;
end
if ( n1 == 1 )
i_save = 0;
j_save = 0;
indx = 0;
i = i_save;
j = j_save;
else
i_save = n1;
n1 = n1 - 1;
j_save = 1;
indx = 1;
i = i_save;
j = j_save;
end
return
end