Fixed _heapsort_a function

[Alex Matulich <alex@xxxxxxxxxxxxxx>]

I wanted to bug-fix a message I sent on 8 Feb regarding the Heapsort
function I posted.  In translating it to EasyLangauge, in which 0
is the lowest array index, from another language in which 1 is the
lowest array index, I missed a couple of things that cause the sort
function to mess up.  Thanks to Bob Fulks for pointing it out.

Below is my original message, with the FIXED version of _heapsort_a.

-Alex

-- original message -----

 Subject: Re: Minlist, Maxlist (sorting an array)
 To: omega-list@xxxxxxxxxx
 Date: Sun, 8 Feb 2004 10:40:53 -0800 (PST)
 From: Alex Matulich <alex@xxxxxxxxxxxxxx>

DH wrote:
>Bob Fulks provided the following code some time ago for sorting any size

In spite of the comment saying it's a "very fast" sort routine,
it's not.  It's a somewhat more efficient variation of a bubble
sort.  This is still an O(N^2) sort (meaning the execution time is
proportional to N^2, the square of the length of the array).

Here's an implementation of heapsort, which I described a
long time ago on this list, before I really learned EasyLanguage:
http://www.purebytes.com/archives/omega/2002/msg05534.html

That version won't work (because it uses the variables I and L,
which are reserved in EL).  Below is a corrected version.  This is
an O(N log N) sort, significantly faster for large arrays.

------------------------------------------------------------------------

{Function: _heapsort_a
 by Alex Matulich
 Adapted from _Numerical Recipes in C_

 This function sorts an array ra[] from index 0 to N.

 Lines marked with [*] are fixed from previous version, to
 work correctly on EasyLanguage arrays which have a lowest
 index of 0, instead of 1.
 }

inputs:
    ra[m](NumericArrayRef),   {array to be sorted}
    N(NumericSimple);         {highest array index}

vars: NN(0), ii(0), ir(0), jj(0), ll(0), rra(0), lp1(true), lp2(true);
if m < N then NN = m else NN = N;
if NN > 0 then begin         {*}
    ll = IntPortion(0.5*NN); {*}
    ir = NN;
    while lp1 begin
        if ll > 0 then begin {*}
            ll = ll-1;
            rra = ra[ll];
        end else begin
            rra = ra[ir];
            ra[ir] = ra[0];
            ir = ir-1;
            if ir = 0 then begin
                ra[0] = rra;
                lp1 = false;
            end;
        end;
        ii = ll;
        jj = ll+ll;
        lp2 = true;
        while lp1 and lp2 and jj <= ir begin
            if jj < ir and ra[jj] < ra[jj+1] then jj = jj+1;
            if rra < ra[jj] then begin
                ra[ii] = ra[jj];
                ii = jj;
                jj = jj+jj;
            end else lp2 = false;
        end;
        ra[ii] = rra;
    end;
end;
_heapsort_a = NN; {dummy return value}

------------------------------------------------------------------------

-Alex