#/***********************************************************
#    mapsort.rb -- µÕ¼ÌÁü¥½¡¼¥È
#***********************************************************/
MAX = 100
MIN = 0

def mapsort(n,  a,  b,  nxt)
    index = []

    for x in 0..MAX; index[x] = -1; end
    (n - 1).downto(0) do |i|
        x = a[i] - MIN;  nxt[i] = index[x];  index[x] = i
    end
    j = 0
    for x in 0..(MAX - MIN)
        i = index[x]
        while (i >= 0) 
            b[j] = a[i];  j += 1;  i = nxt[i]
        end
    end
end

N = 20

a = []; b = []; work = []

printf("Before:")
for i in 0...N
    a[i] = ((MAX - MIN + 1) * rand() + MIN).to_i
    printf(" %d", a[i])
end
printf("\n")
mapsort(N, a, b, work)
printf("After: ")
for i in 0...N; printf(" %d", b[i]); end
printf("\n")

exit 0