Some algorithms for insertion into sorted lists

algorithms.ex

defmodule Algorithms do

  @doc ~S"""
    Insert `elt` into the already sorted `list`.

      iex> Algorithms.insert_sort(1, [])
      [1]

      iex> Algorithms.insert_sort(1, [2,3])
      [1,2,3]

      iex> Algorithms.insert_sort(2, [1,3])
      [1,2,3]

      iex> Algorithms.insert_sort(3, [1,2,4])
      [1,2,3,4]

      iex> Algorithms.insert_sort(4, [1,2,3])
      [1,2,3,4]

    Duplicates are kept.

      iex> Algorithms.insert_sort(1, [1])
      [1, 1]

      iex> Algorithms.insert_sort(2, [1,2])
      [1, 2, 2]

      iex> Algorithms.insert_sort(2, [1,2,3])
      [1, 2, 2, 3]
  """
  @spec insert_sort(elt, [elt]) :: [elt] when elt: var
  def insert_sort(elt, list) do
    {to_rev, rest} = insert_sort([], elt, list, &default_compare/2)
    reverse_concat(to_rev, rest)
  end


  @doc ~S"""
    Insert `elt` into the already sorted `list` using `compare`. In case of equality,
    the order of insertion is kept.

      iex> compare = fn {x, _}, {y, _} ->
      ...>   cond do
      ...>     x  < y -> :lt
      ...>     x == y -> :eq
      ...>     x  > y -> :gt
      ...>   end
      ...> end
      iex> Algorithms.insert_sort({1, "a"}, [{2, "b"}, {3, "c"}], compare)
      [{1, "a"}, {2, "b"}, {3, "c"}]
      iex> Algorithms.insert_sort({2, "b"}, [{1, "a"}, {3, "c"}], compare)
      [{1, "a"}, {2, "b"}, {3, "c"}]
      iex> Algorithms.insert_sort({1, "a2"}, [{1, "a1"}], compare)
      [{1, "a1"}, {1, "a2"}]
      iex> Algorithms.insert_sort({2, "b1"}, [{1, "a"}, {2, "b2"}], compare)
      [{1, "a"}, {2, "b2"}, {2, "b1"}]
  """
  @spec insert_sort(elt, [elt], (elt, elt -> :lt | :eq | :gt)) :: [elt] when elt: var
  def insert_sort(elt, list, compare) do
    {to_rev, rest} = insert_sort([], elt, list, compare)
    reverse_concat(to_rev, rest)
  end


  @doc ~S"""
    Append `next` to `to_rev` after this latter has been reversed.

      iex> Algorithms.reverse_concat([], [])
      []

      iex> Algorithms.reverse_concat([], [1,2])
      [1,2]

      iex> Algorithms.reverse_concat([1,2], [9,10])
      [2,1,9,10]

      iex> Algorithms.reverse_concat([1,2,3], [])
      [3,2,1]
  """
  @spec reverse_concat([x], [x]) :: [x] when x: var
  def reverse_concat(to_rev, next)
  def reverse_concat([], next), do: next
  def reverse_concat([x|xs], next), do: reverse_concat(xs, [x|next])


  @doc ~S"""
    Merge two sorted list into a sorted list.

      iex> Algorithms.merge_sort([], [])
      []

      iex> Algorithms.merge_sort([1], [1])
      [1,1]

      iex> Algorithms.merge_sort([], [1])
      [1]

      iex> Algorithms.merge_sort([1], [])
      [1]

      iex> Algorithms.merge_sort([1,2], [1])
      [1,1,2]

      iex> Algorithms.merge_sort([1,2,5], [1,3,4])
      [1,1,2,3,4,5]

      iex> Algorithms.merge_sort([3,5], [1,2,4])
      [1,2,3,4,5]

      iex> Algorithms.merge_sort([1,2,4], [3,5])
      [1,2,3,4,5]

      iex> Algorithms.merge_sort([3,5], [6,7,8])
      [3,5,6,7,8]

      iex> Algorithms.merge_sort([6,7,8], [3,5])
      [3,5,6,7,8]
  """
  @spec merge_sort([x], [x]) :: [x] when x: var
  def merge_sort(xs, ys) do
    merge_sort(xs, ys, &default_compare/2)
  end


  @spec merge_sort([x], [x], (x, x -> :lt | :eq | :gt)) :: [x] when x: var
  def merge_sort(xs, ys, compare) do
    {to_rev, rest} = merge_sort([], xs, ys, compare)
    reverse_concat(to_rev, rest)
  end


  # -- Private


  @spec default_compare(elt, elt) :: :lt | :eq | :gt when elt: var
  defp default_compare(x,y) do
    cond do
      x  < y -> :lt
      x == y -> :eq
      x  > y -> :gt
    end
  end


  @spec merge_sort([x], [x], [x], (x, x -> :lt | :eq | :gt)) :: {[x],[x]} when x: var
  defp merge_sort(acc, [], [], _) do
    {acc, []}
  end


  defp merge_sort(acc, xs, [], _) do
    {acc, xs}
  end


  defp merge_sort(acc, [], ys, _) do
    {acc, ys}
  end


  defp merge_sort(acc, xss = [x|xs], yss = [y|ys], compare) do
    case compare.(x, y) do
      :lt -> merge_sort([x|acc], xs, yss, compare)
      :eq -> merge_sort([x|[y|acc]], xs, ys, compare)
      :gt -> merge_sort([y|acc], xss, ys, compare)
    end
  end


  defp insert_sort(acc, elt, [], _) do
    {[elt | acc], []}
  end
  defp insert_sort(acc, elt, list = [x | xs], compare) do
    case compare.(elt, x) do
      :lt -> {[elt | acc], list}
      :eq -> insert_sort([x | acc], elt, xs, compare)
      :gt -> insert_sort([x | acc], elt, xs, compare)
    end
  end

end