The Wiki site claims the Gnome Sort to be the simplest, but it turns out that converting the Bubble Sort to HP GTO-ese is actually simpler, and has faster run times too.

Pseudo code:

procedure bubbleSort( A : list of sortable items ) defined as:

  n := length( A )

  do

    swapped := false

    n := n - 1

    for each i in 0 to n - 1  inclusive do:

      if A[ i ] > A[ i + 1 ] then

        swap( A[ i ], A[ i + 1 ] )

        swapped := true

      end if

    end for

  while swapped

end procedure

Program listing:

S001	LBL S	

S002	STO Z		bbb.eee

S003	CF 0		start of do-while

S004	0.001	

S005	STO- Z		bbb.(eee - 1)

S006	RCL Z	

S007	STO I		for (I = bbb; I <= eee - 1; i++)

S008	RCL I	

S009	1	

S010	+	

S011	STO J	

S012	RCL(J)		A[i+1]

S013	RCL(I)		A[i]

S014	x<=y?	

S015	GTO S020	

S016	STO(J)		A[i+1] = A[i]

S017	RDN	

S018	STO(I)		A[i] = A[i+1]

S019	SF 0		swapped = true

S020	ISG I	

S021	GTO S008	

S022	FS? 0		swapped = true?

S023	GTO S003	

S024	RTN	

LN=78	CK=B7E4	

And finally, some timings:

21 registers, 10.030:  23 seconds

21 registers, 10.030:  24 seconds

101 registers, 10.110:  ~10 minutes

So, even the much-detested Bubble Sort is superior to the cutesy Gnome Sort I started this project with.

Bubble sort isn't bad, if the items are "in almost sort order" at the beginning of the algorithm. If all items are already sorted, a single pass is all to find that out. Bubble sort is stable, too, that is, it leaves the original sorting of items considered "equal" by the comparison algorithm intact.