
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Task

Sort an array of elements using the Shell sort algorithm, a diminishing increment sort.

The Shell sort   (also known as Shellsort or Shell's method)   is named after its inventor, Donald Shell, who published the algorithm in 1959.

Shell sort is a sequence of interleaved insertion sorts based on an increment sequence.
The increment size is reduced after each pass until the increment size is 1.

With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case".

Any sequence will sort the data as long as it ends in 1, but some work better than others.

Empirical studies have shown a geometric increment sequence with a ratio of about 2.2 work well in practice.
[1]

Other good sequences are found at the On-Line Encyclopedia of Integer Sequences.




*        Shell sort                24/06/2016 
SHELLSRT CSECT
         USING  SHELLSRT,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         "
         ST     R15,8(R13)         " 
         LR     R13,R15            "
         L      RK,N               incr=n
         SRA    RK,1               incr=n/2
         DO WHILE=(LTR,RK,P,RK)    do while(incr>0)
         LA     RI,1(RK)             i=1+incr    
         DO WHILE=(C,RI,LE,N)        do i=1+incr to n
         LR     RJ,RI                  j=i
         LR     R1,RI                  i
         SLA    R1,2                   .
         L      RT,A-4(R1)             temp=a(i)
         LR     R2,RK                  incr
         LA     R2,1(R2)               r2=incr+1
         LR     R3,RJ                  j
         SR     R3,RK                  j-incr
         SLA    R3,2                   *.
         LA     R3,A-4(R3)             r3=@a(j-incr)
         LR     R4,RK                  incr
         SLA    R4,2                   r4=incr*4
         LR     R5,RJ                  j
         SLA    R5,2                   .
         LA     R5,A-4(R5)             @a(j)
*        do while j-incr>=1 and a(j-incr)>temp 
         DO WHILE=(CR,RJ,GE,R2,AND,C,RT,LT,0(R3))
         L      R0,0(R3)                 a(j-incr)
         ST     R0,0(R5)                 a(j)=a(j-incr)
         SR     RJ,RK                    j=j-incr
         LR     R5,R3                    @a(j)
         SR     R3,R4                    @a(j-incr)=@a(j-incr)-incr*4
         ENDDO  ,                      end do
         ST     RT,0(R5)               a(j)=temp
         LA     RI,1(RI)               i=i+1
         ENDDO  ,                    end do
         IF     C,RK,EQ,=F'2'        if incr=2
         LA     RK,1                   incr=1
         ELSE   ,                    else
         LR     R5,RK                  incr
         M      R4,=F'5'               *5
         D      R4,=F'11'              /11
         LR     RK,R5                  incr=incr*5/11
         ENDIF  ,                    end if
         ENDDO  ,                  end do
         LA     R3,PG              pgi=0
         LA     RI,1               i=1
         DO     WHILE=(C,RI,LE,N)  do i=1 to n
         LR     R1,RI                i
         SLA    R1,2                 .
         L      R2,A-4(R1)           a(i)
         XDECO  R2,XDEC              edit a(i)
         MVC    0(4,R3),XDEC+8       output a(i)
         LA     R3,4(R3)             pgi=pgi+4
         LA     RI,1(RI)             i=i+1
         ENDDO  ,                  end do
         XPRNT  PG,L'PG            print buffer
         L      R13,4(0,R13)       epilog 
         LM     R14,R12,12(R13)    "
         XR     R15,R15            "
         BR     R14                exit
A     DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
      DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
N        DC     A((N-A)/L'A)       number of items of a
PG       DC     CL80' '            buffer
XDEC     DS     CL12               temp for xdeco
         YREGS
RI       EQU    6                  i
RJ       EQU    7                  j
RK       EQU    8                  incr
RT       EQU    9                  temp
         END    SHELLSRT