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



/*REXX program  sorts  and displays  a  stemmed array  using the  comb sort  algorithm. */
call gen                                         /*generate the   @   array elements.   */
call show    'before sort'                       /*display the  before  array elements. */
                            say  copies('▒', 60) /*display a separator line  (a fence). */
call combSort    #                               /*invoke the comb sort (with # entries)*/
call show    ' after sort'                       /*display the   after  array elements. */
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
combSort: procedure expose @.;   parse arg N     /*N:  is the number of  @  elements.   */
          g= N-1                                 /*G:  is the gap between the sort COMBs*/
                 do  until g<=1 & done;  done= 1 /*assume sort is done  (so far).       */
                 g= g * 0.8  % 1                 /*equivalent to:   g= trunc( g / 1.25) */
                 if g==0  then g= 1              /*handle case of the gap is too small. */
                    do j=1  until $>=N;  $= j+g  /*$:     a temporary index  (pointer). */
                    if @.j>@.$  then do;   _= @.j;    @.j= @.$;   @.$= _;   done= 0;   end
                    end   /*j*/
                 end     /*until*/               /* [↑]  swap two elements in the array.*/
          return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen: @.=;     @.1  = '----polygon---  sides'  ;              @.12 = "dodecagon         12"
              @.2  = '============== =======' ;              @.13 = "tridecagon        13"
              @.3  = 'triangle           3'   ;              @.14 = "tetradecagon      14"
              @.4  = 'quadrilateral      4'   ;              @.15 = "pentadecagon      15"
              @.5  = 'pentagon           5'   ;              @.16 = "hexadecagon       16"
              @.6  = 'hexagon            6'   ;              @.17 = "heptadecagon      17"
              @.7  = 'heptagon           7'   ;              @.18 = "octadecagon       18"
              @.8  = 'octagon            8'   ;              @.19 = "enneadecagon      19"
              @.9  = 'nonagon            9'   ;              @.20 = "icosagon          20"
              @.10 = 'decagon           10'   ;              @.21 = "hectogon         100"
              @.11 = 'hendecagon        11'   ;              @.22 = "chiliagon       1000"
                                                             @.23 = "myriagon       10000"
                         do #=1  while  @.#\=='';  end    /*find how many elements in @ */
      #= #-1;     w= length(#);           return          /*adjust # because of DO loop.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show:     do k=1  for #; say right('element',15) right(k,w)  arg(1)":"  @.k;  end;  return