elixir: order a list of numbers without built-in sort function

If I have a list that varies in length each time and I want to sort it from lowest to highest, how would I do that?

If I have: [-5, -23, 5, 0, 23, 0.7, -6, 23, 67]

I want: [-23, -6, -5, 0, 0.7, 5, 23, 23, 67]

I tried to use a for loop to iterate the list and create a new list to receive the numbers but doesn't look like it's gonna work. maybe i can use Enum function instead, but i'm really without ideas on this one.

Solution

If you cannot use Enum.sort, you have to implement your own sorting algorithm.

Elixir is an immutable language, so popular algorithms that require in-place operations like Quicksort do not work well in Elixir. Here is an implementation of Mergesort:

defmodule Example do
  def merge_sort([]), do: []
  def merge_sort([_] = list), do: list

  def merge_sort(list) when is_list(list) do
    len = length(list)
    {a, b} = Enum.split(list, div(len, 2))
    a = merge_sort(a)
    b = merge_sort(b)
    merge(a, b, [])
  end

  defp merge([], b, acc), do: Enum.reverse(acc) ++ b
  defp merge(a, [], acc), do: Enum.reverse(acc) ++ a

  defp merge([a_head | a_tail] = a, [b_head | b_tail] = b, acc) do
    if a_head <= b_head do
      merge(a_tail, b, [a_head | acc])
    else
      merge(a, b_tail, [b_head | acc])
    end
  end
end

Running:

iex> Example.merge_sort([-5, -23, 5, 0, 23, 0.7, -6, 23, 67])
[-23, -6, -5, 0, 0.7, 5, 23, 23, 67]

Just for fun, here is reverse and split, if you don't want to use Enum at all:

defp reverse(list), do: reverse(list, [])
defp reverse([], acc), do: acc
defp reverse([h | t], acc), do: reverse(t, [h | acc])

defp split(list, n), do: split(list, [], n)
defp split(a, b, 0), do: {reverse(b), a}
defp split([h | a], b, n), do: split(a, [h | b], n - 1)

^{We can even simplify {reverse(b), a}, to {b, a} in this case, because there's no need to preserve the item order when splitting, since the result gets sorted anyway.}