# Natural Sorting algorithms

Hi,
we are trying to sort things naturally in ExDoc.

Can anybody recommend a natural sorting algorithm implementation in Elixir?
I have a a few but I am looking for options,
Thank you.

How do you define â€śnaturalâ€ť?

Things that come to mind:

• ignore case
• ignore diacritics
• `2 < 10`
1 Like

Mostly. Case should not be ignored, but order should be: `A, a, B, b`, and not `A, B, a, b` as sorting by ASCII code does.

I have this hacky solution which should work but probably isnâ€™t optimal:

``````Enum.sort_by(~w(A B a b), &{String.downcase(&1), &1})
``````
1 Like

FWIW, I have proposed the custom optimized sorter: Sort items "naturally" in menu, summary, function list, etc. Â· Issue #1440 Â· elixir-lang/ex_doc Â· GitHub

4 Likes

EDIT: the implementation is correct, I had the wrong input

The problem with this approach is that it returns different results depending on the initial order for the same list shuffled.

``````iex(16)> Enum.sort_by(~w(A B a b), &{String.downcase(&1), &1})
["A", "a", "B", "b"]

iex(17)> Enum.sort_by(~w(a B B b), &{String.downcase(&1), &1})
["a", "B", "B", "b"]
``````

Actually I have reported this very same issue to this library just a few hours ago: Enumerables are sorted depending on their initial order Â· Issue #4 Â· BinaryNoggin/natural_order Â· GitHub

1 Like

Thank you Aleksei for your contribution to the discussion, later one with more time, I will look in detail and see how I can apply those to the NaturalOrder library. There are a few lessons to take from the discussion.

1 Like

Well, this is obvious implication of the fact that `Enum.sort*` functions are using stable sort algorithms.

Iâ€™m sorry if I misunderstood your comment, but this example is not using the same list shuffled, these are different lists. I believe the result provided is the expected one?

If I reuse the example from your issue it seems fine too:

``````iex(1)> ~W(a A b) |> Enum.sort_by(&{String.downcase(&1), &1})
["A", "a", "b"]
iex(2)> ~W(A b a) |> Enum.sort_by(&{String.downcase(&1), &1})
["A", "a", "b"]
``````
1 Like

You are right. I messed up with the input. Your implementation.

1 Like

We updated NaturalSort with changes from @eksperimental. Thanks for fixing those bugs.

2 Likes

Just for reference, here is the same approach with a custom comparator. I didnâ€™t bench these but since it doesnâ€™t build tuples it is probably faster:

``````defmodule Natural do
def natural_sort(enumerable) do
Enum.sort(enumerable, __MODULE__)
end

def compare(x, y) do
case do_compare(String.upcase(x), String.upcase(y)) do
:eq -> do_compare(x, y)
lt_or_gt -> lt_or_gt
end
end

defp do_compare(x, x), do: :eq
defp do_compare(x, y) when x > y, do: :gt
defp do_compare(_, _), do: :lt
end
``````
1 Like