merge_sort.exs

defmodule MergeSort do
  @spec sort([number]) :: [number]
  def sort(list) do
    case Enum.count(list) do
      0 -> list
      1 -> list

      _ ->
        midpoint = Enum.count(list) / 2 |> ceil()
        {head_list, tail_list} = Enum.split(list, midpoint)

        sorted_head_list = sort(head_list)
        sorted_tail_list = sort(tail_list)

        combine(sorted_head_list, sorted_tail_list)
    end
  end

  defp combine(head_list, tail_list),
    do: combine([], head_list, tail_list)

  defp combine(acc, [], tail_list),
    do: acc ++ tail_list

  defp combine(acc, head_list, []),
    do: acc ++ head_list

  defp combine(acc, head_list, tail_list) do
    {item, new_head_list, new_tail_list} = take_next_item(head_list, tail_list)

    new_acc = acc ++ [item]

    combine(new_acc, new_head_list, new_tail_list)
  end

  defp take_next_item(head_list, tail_list) do
    [head_value | new_head_list] = head_list
    [tail_value | new_tail_list] = tail_list

    cond do
      head_value < tail_value ->
        {head_value, new_head_list, tail_list}

      true ->
        {tail_value, head_list, new_tail_list}
    end
  end
end

list = []
IO.inspect MergeSort.sort(list)

list = [5]
IO.inspect MergeSort.sort(list)

list = [5, 3, 8, 1, 6, 2]
IO.inspect MergeSort.sort(list)

list = [5, 3, 8, 1, 6, 2, 15, -2]
IO.inspect MergeSort.sort(list)