Sorting algorithms/Comb sort

You are encouraged to solve this task according to the task description, using any language you may know.

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

Implement a   comb sort.



The Comb Sort is a variant of the Bubble Sort.

Like the Shell sort, the Comb Sort increases the gap used in comparisons and exchanges.

Dividing the gap by   



(
1
−

e

−
φ



)

−
1


≈
1.247330950103979


{\displaystyle (1-e^{-\varphi })^{-1}\approx 1.247330950103979}

    works best, but    1.3   may be more practical.



Some implementations use the insertion sort once the gap is less than a certain amount.



Also see

   the Wikipedia article:   Comb sort.


Variants:

 Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings.
 Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small).   Comb sort with a low gap isn't much better than the Bubble Sort.


Pseudocode:

function combsort(array input)
    gap := input.size //initialize gap size
    loop until gap = 1 and swaps = 0
        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.25)
        if gap < 1
          //minimum gap is 1
          gap := 1
        end if
        i := 0
        swaps := 0 //see Bubble Sort for an explanation
        //a single "comb" over the input list
        loop until i + gap >= input.size //see Shell sort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swaps := 1 // Flag a swap has occurred, so the
                           // list is not guaranteed sorted
            end if
            i := i + 1
        end loop
    end loop
end function



*        Comb sort                 23/06/2016
COMBSORT CSECT
         USING  COMBSORT,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      R2,N               n
         BCTR   R2,0               n-1
         ST     R2,GAP             gap=n-1
         DO     UNTIL=(CLC,GAP,EQ,=F'1',AND,CLI,SWAPS,EQ,X'00') repeat
         L      R4,GAP               gap                             |
         MH     R4,=H'100'           gap*100                         |
         SRDA   R4,32                .                               |
         D      R4,=F'125'           /125                            |
         ST     R5,GAP               gap=int(gap/1.25)               |
         IF     CLC,GAP,LT,=F'1'     if gap<1 then  -----------+     |
         MVC    GAP,=F'1'              gap=1                   |     |
         ENDIF  ,                    end if  <-----------------+     |
         MVI    SWAPS,X'00'          swaps=false                     |
         LA     RI,1                 i=1                             |
         DO     UNTIL=(C,R3,GT,N)    do i=1 by 1 until i+gap>n  ---+ |
         LR     R7,RI                  i                           | |
         SLA    R7,2                   .                           | |
         LA     R7,A-4(R7)             r7=@a(i)                    | |
         LR     R8,RI                  i                           | |
         A      R8,GAP                 i+gap                       | |
         SLA    R8,2                   .                           | |
         LA     R8,A-4(R8)             r8=@a(i+gap)                | |
         L      R2,0(R7)               temp=a(i)                   | |
         IF     C,R2,GT,0(R8)          if a(i)>a(i+gap) then  ---+ | |
         MVC    0(4,R7),0(R8)            a(i)=a(i+gap)           | | |
         ST     R2,0(R8)                 a(i+gap)=temp           | | |
         MVI    SWAPS,X'01'              swaps=true              | | |
         ENDIF  ,                      end if  <-----------------+ | |
         LA     RI,1(RI)               i=i+1                       | |
         LR     R3,RI                  i                           | |
         A      R3,GAP                 i+gap                       | |
         ENDDO  ,                    end do  <---------------------+ |
         ENDDO  ,                  until gap=1 and not swaps  <------+
         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
GAP      DS     F                  gap
SWAPS    DS     X                  flag for swaps
PG       DS     CL80               output buffer
XDEC     DS     CL12               temp for edit
         YREGS
RI       EQU    6                  i
         END    COMBSORT