(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file shsort.mos                                     *
  * ```````````````                                     *
  * Example for the use of the Mosel language           *
  * (Sort an array of numbers into numerical order)     *
  *                                                     *
  * Implements Shell' method: first sort, by straight   *
  * insertion, small groups of numbers. Next, combine   *
  * several small groups and sort them (possibly repeat *
  * this step). Finally, sort the whole list of numbers.*
  *                                                     *
  * The spacings between the numbers of groups sorted   *
  * on each pass through the data are called the        *
  * increments. A good choice is the sequence which     *
  * can be generated by the recurrence                  *
  * i(1)=1, i(k+1)=3i(k)+1, k=1,2,...                   *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: S. Heipcke, 2001                        *
  *******************************************************!)

model ShellSort                ! Start a new model

declarations
 N: integer                    ! Size of array ANum
 ANum: array(range) of real    ! Unsorted array of numbers
end-declarations

 N:=50
 forall(i in 1..N)
  ANum(i):=round(random*100)

 writeln("Given list of numbers (size: ", N, "): ")
 forall(i in 1..N) write(ANum(i), " ")
 writeln

 inc:=1                        ! Determine the starting increment
 repeat                         
   inc:=3*inc+1
 until (inc>N)  
 
 repeat                        ! Loop over the partial sorts
   inc:=inc div 3
   forall(i in inc+1..N) do    ! Outer loop of straight insertion
     v:=ANum(i)
     j:=i
     while (ANum(j-inc)>v) do  ! Inner loop of straight insertion
       ANum(j):=ANum(j-inc)
       j -= inc
       if j<=inc then break; end-if
     end-do
     ANum(j):= v     
   end-do  
 until (inc<=1)
 
 writeln("Ordered list: ")
 forall(i in 1..N) write(ANum(i), " ")
 writeln
 
end-model