#!/usr/bin/ruby
def merge(a, l, r)
    nl = l.length
    nr = r.length
    i, j, k = [0]*3
    while i < nl and j < nr
        if l[i] <= r[j]
            a[k] = l[i]
            i += 1
        else
            a[k] = r[j]
            j += 1
        end
        k += 1
    end
    while i < nl
        a[k] = l[i]
        i += 1
        k += 1
    end
    while j < nl
        a[k] = r[j]
        j +=1
        k +=1
    end
    return a
end

def mergesort(a)
    n = a.length
    return a if n < 2
    mid = n/2
    l, r = Array.new(mid), Array.new(n-mid)
    for i in (0..mid-1) do
        l[i] = a[i]
    end
    for i in (mid..n-1) do
        r[i-mid] = a[i]
    end
    mergesort(l)
    mergesort(r)
    return merge(a, l,r)
end

#ar = STDIN.gets.chomp.split(" ").map{|x|x.to_i};
a = mergesort([42, 37, 2, 5, 7, 8, 1, 17])
puts a