Heapsort

[Werner]

sorts a contiguous block aaa,bbb. Uses M,N,O,Q
113 bytes including END

Code:

01>LBL"HSORT"   -- In: a,b
02 ENTER
03 FRC
04  E3
05 x
06 X<Y?         -- less than 2 elements
07 RTN
08 STO O        -- O: b
09 X<>Y
10 1
11 -
12 STO M        -- M: a-1,b
13 INT
14 -
15 2
16 /
17 INT
18 STO N        -- N: INT(n/2), n = b-a+1

19>LBL 02       -- heapify
20 RCL N
21 RCL M
22 +
23 XEQ 10
24 DSE N
25 GTO 02

26>LBL 03       -- sort heap
27  E-3
28 ST- L
29 LASTX
30 ISG X
31 X=0?
32 RTN
33 RCL IND X
34 X<> IND O
35 STO IND Y
36 Rv
37 DSE O
38 XEQ 10
39 GTO 03

40>LBL 04       -- two leaves
41 RCL IND Y
42 RCL IND Y
43 X<Y?
44 CLX
45 RCL IND Q
46 X<>Y
47 X<=Y?
48 RTN
49 X<> IND Q
50 STO IND T
51 R^

52>LBL 10       -- SiftDown(i,b) L: a-1,b X: i,b
53 STO Q        -- Q:i
54 ST+ X
55 LASTX
56 -
57 ENTER
58 ISG Y        -- X:2i    Y:2i+1
59 GTO 04
60 DSE Y
61 RTN          -- no leaves
62 RCL IND Q    -- one leaf & end
63 RCL IND Y
64 X<=Y?
65 RTN
66 X<> IND Q
67 STO IND Z
68 END

Cheers, Werner