function mergesort(e,d)

	if e < d then
		local meio = math.ceil((e+d)/2)
		mergesort(e,meio-1)			
		mergesort(meio,d)
		merge(e,meio,d)			
	end
end

-- faz merge de duas listas 
-- v[e] ate v[meio] e 
-- v[meio+1] ateh v[d]
-- sem suporte a duplicados 
--
function merge(e,meio,d)

	local a  = e
	local b  = meio
	local w  = {}
	local wi = 1

	-- intercala as listas 
	while (a <= meio-1) and (b <= d) do 

		if v[a] < v[b] then
			w[wi] = v[a]
			wi = wi + 1
			a = a + 1
		else 
			w[wi] = v[b]
			wi = wi + 1
			b = b + 1
		end
	end

	-- verifica se sobrou algum a processar as listas
	while a <= meio-1 do 
		w[wi] = v[a]
		wi = wi + 1
		a = a + 1
	end
	
	while b <= d do 
		w[wi] = v[b]
		wi = wi + 1
		b = b + 1
	end
	
	-- copia os elementos intercalados de volta na lista
	local i = e
	for k=1, wi-1 do 
		v[i] = w[k]
		i = i + 1
	end

end

	v = { 9, 6, 3, 5, 2, 7, 10, 12, 1 }
	N = table.getn(v)
	
	print( table.concat(v,",") ) 
	mergesort(1, N)
	print( table.concat(v,",") )