merge_and_dedup.exs

defmodule Util do
  def merge_and_dedup(a, b) do
    internal_merge_and_dedup(Enum.reverse(a), Enum.reverse(b), [])
  end

  defp internal_merge_and_dedup([h1 | t1] = l1, [h2 | t2] = l2, []) do
    if h1 < h2 do
      internal_merge_and_dedup(l1, t2, [h2])
    else
      internal_merge_and_dedup(t1, l2, [h1])
    end
  end

  defp internal_merge_and_dedup([h1 | t1] = l1, [h2 | t2] = l2, [last | _] = acc) do
    cond do
      h1 === last ->
        internal_merge_and_dedup(t1, l2, acc)
      h2 === last ->
        internal_merge_and_dedup(l1, t2, acc)
      h1 === h2 ->
        internal_merge_and_dedup(t1, t2, [h1 | acc])
      h1 < h2 ->
        internal_merge_and_dedup(l1, t2, [h2 | acc])
      h1 > h2 ->
        internal_merge_and_dedup(t1, l2, [h1 | acc])
    end
  end

  defp internal_merge_and_dedup([], [h | t], [last | _] = acc) do
    if h === last do
      internal_merge_and_dedup([], t, acc)
    else
      internal_merge_and_dedup([], t, [h | acc])
    end
  end

  defp internal_merge_and_dedup([], [h | t], []) do
    internal_merge_and_dedup([], t, [h])
  end

  defp internal_merge_and_dedup([], [], acc) do
    acc
  end

  defp internal_merge_and_dedup(l, [], acc) do
    #reuse the code
    internal_merge_and_dedup([], l, acc)
  end

  ###########################################
  def rand_list(n, r) do
    internal_rand_list(n, r, [])
  end

  defp internal_rand_list(0, _, acc) do
    acc
  end

  defp internal_rand_list(n, r, acc) do
    internal_rand_list(n-1, r, [:rand.uniform(r) | acc])
  end

  ##########################################
  def unit_test do
    #by the pidgeon hole principle collistions will occur
    a = Util.rand_list(10000, 1000) |> Enum.sort
    b = Util.rand_list(10000, 1000) |> Enum.sort

    {t1, method1} = :timer.tc(fn ->
      a ++ b
      |> Enum.sort
      |> Enum.uniq
      end)

    {t2, method2} = :timer.tc(fn -> Util.merge_and_dedup(a, b) end)

    #IO.inspect([t1, t2])
    #IO.puts(method1 === method2)
    method1 === method2 and t1 > 2*t2 # ;)
  end
end

Enum.reduce(1..100, true, fn _, acc -> acc and Util.unit_test() end)
|> IO.puts