mergesort.ex

defmodule Mergesort do
  @moduledoc """
  Documentation for `Mergesort`.

  Source: https://gist.github.com/coproduto/1c833523680628cd25884e047e64bd7b
  """

  @doc """
  Sorts a list.


  """
  def merge_sort([]), do: []

  def merge_sort(list) do
    list
    |> Enum.map(fn x -> [x] end)
    |> merge_lists()
  end

  def merge_lists([list]), do: list

  def merge_lists(lists) do
    lists
    |> merge_pass()
    |> merge_lists()
  end

  def merge_pass(list), do: merge_pass(list, [])
  defp merge_pass([], acc), do: acc

  defp merge_pass([xs], acc), do: [xs | acc]

  defp merge_pass([xs, ys | rest], acc) do
    merge_pass(rest, [merge(xs, ys) | acc])
  end

  def merge(xs, []), do: xs

  def merge([], ys), do: ys

  def merge(left = [x | xs], right = [y | ys]) do
    if y <= x do
      [y | merge(left, ys)]
    else
      [x | merge(xs, right)]
    end
  end
end

mergesort_test.exs

defmodule MergesortTest do
  use ExUnit.Case
  doctest Mergesort

  @list_size 1000

  test "Mergesort sorts a shuffled list" do
    shuffled_list =
      1..@list_size
      |> Enum.shuffle()

    assert Mergesort.merge_sort(shuffled_list) == Enum.sort(shuffled_list)
  end

  test "Mergesort sorts an ordered list" do
    ordered_list =
      1..@list_size
      |> Enum.shuffle()
      |> Enum.sort()

    assert Mergesort.merge_sort(ordered_list) == ordered_list
  end

  test "Mergesort sorts a reverse ordered list" do
    reverse_ordered_list =
      1..@list_size
      |> Enum.shuffle()
      |> Enum.sort()
      |> Enum.reverse()

    assert Mergesort.merge_sort(reverse_ordered_list) == Enum.sort(reverse_ordered_list)
  end

  test "Tests for auxiliary function merge_lists/1" do
    list_with_one_element_which_is_a_list = [[1]]

    assert Mergesort.merge_lists(list_with_one_element_which_is_a_list) == [1]

    list_for_this_test = [
      [1],
      [5],
      [2],
      [4]
    ]

    assert Mergesort.merge_lists(list_for_this_test) == [1, 2, 4, 5]

    list_for_this_test = [[1, 2, 3, 5], [2, 3, 4, 8]]

    assert Mergesort.merge_lists(list_for_this_test) == [1, 2, 2, 3, 3, 4, 5, 8]

    list_for_this_test = [[1, 2, 5], [2]]

    assert Mergesort.merge_lists(list_for_this_test) == [1, 2, 2, 5]

    list_for_this_test = [[1, 2, 5], [2], [0]]

    assert Mergesort.merge_lists(list_for_this_test) == [0, 1, 2, 2, 5]
  end

  test "Tests for auxiliary function merge_pass/2 ONE PASS" do
    list_with_one_element_which_is_a_list = [[1]]

    assert Mergesort.merge_pass(list_with_one_element_which_is_a_list) == [[1]]

    list_for_this_test = [
      [2],
      [1],
      [5],
      [4]
    ]

    assert Mergesort.merge_pass(list_for_this_test) ==
             [[4, 5], [1, 2]]

    list_for_this_test = [
      [2],
      [1],
      [5],
      [4],
      [0]
    ]

    assert Mergesort.merge_pass(list_for_this_test) ==
             [[0], [4, 5], [1, 2]]
  end

  test "Tests for auxiliary function merge_pass/2 TWO PASSES" do
    list_for_this_test = [[1], [5], [2], [3], [8], [2], [4], [3]]

    assert Mergesort.merge_pass(list_for_this_test)
           |> Mergesort.merge_pass() ==
             [[1, 2, 3, 5], [2, 3, 4, 8]]
  end

  test "Tests for auxiliary function merge/2" do
    assert Mergesort.merge([1, 3], [2, 4]) == [1, 2, 3, 4]

    first_list =
      1..@list_size
      |> Enum.shuffle()
      |> Enum.take(div(@list_size, 2))
      |> Enum.sort()

    second_list =
      1..@list_size
      |> Enum.shuffle()
      |> Enum.take(div(@list_size, 2))
      |> Enum.sort()

    assert Mergesort.merge(first_list, second_list) == Enum.sort(first_list ++ second_list)
  end
end