#Shell Sort implementation(Diminishing Increment Sort)
#Time-complexity: O(n^2), In-place
#will be using Knuth series :3n+1

def shell_sort(a)
    n=a.length
    h=1
    
    while (h<n/3)  #for computing increment factor "h"
        h= (3*h)+1
    end
    
    while h>=1
    # Logic of insertion sort with inrement steps of "h"
        for i in h...n
            j=i
            while j>=h
                if a[j-h]>a[j]
                    temp=a[j]
                    a[j]=a[j-h]
                    a[j-h]=temp
                end
                j-=h
            end
        end
        h/=3
    end
    
    return a
    
end

puts(shell_sort([0,5,4,7,1,8,9,3,7,1,4,2,8,6]))