n=15;
A = Array.new(n) { |j| rand(0..9)}
B = []
for j in (0..n-1) do
  B[j] = 0
end
print("#{A}\n")
k=1
while (k<n)
    t=0
    while ((t+k)<=n)
      q=t+k
      if(t+2*k>=n)
        r=n
      else
        r=t+2*k
      end
      p0=t
      q0=q
      s0=t
      while ((p0!=q) || (q0!=r))
        if ((p0<q) && (((q0==r)||((q0<r) && (A[p0]<=A[q0]))))) 
             B[s0]=A[p0]
             p0=p0+1
             s0=s0+1
        else
             B[s0]=A[q0]
             q0=q0+1
             s0=s0+1
        end
      end 
      t=r
    end
    k=k*2
    for i in (0..n-1) do
      A[i]=B[i]
    end
end
print("#{A}\n")