mergesort.ex

defmodule MergeSort do
  @spec sort(list()) :: list()
  def sort([]), do: []
  def sort([h]), do: [h]

  def sort([_ | _] = list) do
    {left, right} = divide(list)

    left_sorted = sort(left)
    right_sorted = sort(right)

    merge_sorted(left_sorted, right_sorted)
  end

  @spec divide(list()) :: {list(), list({})}
  def divide(list) do
    Enum.split(list, ceil(length(list) / 2))
  end

  @spec merge_sorted(list(), list()) :: list()
  def merge_sorted(left, right) do
    do_merge_sorted(left, right, [])
  end

  @spec do_merge_sorted(list(), list(), list()) :: list()
  defp do_merge_sorted([], [], merged), do: Enum.reverse(merged)
  defp do_merge_sorted([], [h | t], merged), do: do_merge_sorted([], t, [h | merged])
  defp do_merge_sorted([h | t], [], merged), do: do_merge_sorted(t, [], [h | merged])

  defp do_merge_sorted([hl | tl] = left, [hr | tr] = right, merged) do
    if hl < hr do
      do_merge_sorted(tl, right, [hl | merged])
    else
      do_merge_sorted(left, tr, [hr | merged])
    end
  end
end