Stability of Enum.sort/2

[Jamiel Almeida]

Hey guys, I'm studying Elixir, and noticing that as of 0.12.5 Enum.sort/2 isn't a stable implementation of Merge Sort.

It is described as a merge sort in:
http://elixir-lang.org/docs/master/Enum.html#sort/2

Yet, as mentioned it doesn't preserve the order of the items.

I believe that this is a property desired in a core sorting method so that it can be used to implement multiple-pass sorts.

By multiple-pass sort what I mean is:
sorted_info = get_student_info |> sort_by_student_number |> sort_by_first_name |> sort_by_last_name

If the implementation of sort isn't stable, I can't guarantee that after I sort them by student number, students with the same name and last name will remain in student number order.

Here are snipets of code that show it is *almost* stable, but elements of the same "weight" are in reverse (?)

Example code:

iex(1)> Enum.sort ["some","kind","of","monster"], &(String.length(&1) > String.length(&2))

["monster", "kind", "some", "of"]

iex(2)> Enum.sort ["some","kind","of","monster"], &(String.length(&1) < String.length(&2))

["of", "kind", "some", "monster"]

iex(3)> Enum.sort ["once","upon","a","time"], &(String.length(&1) > String.length(&2))    

["time", "upon", "once", "a"]

iex(4)> Enum.sort ["once","upon","a","time"], &(String.length(&1) < String.length(&2))

["a", "time", "upon", "once"]

iex(5)> Enum.sort ["upon","once","a","time"], &(String.length(&1) < String.length(&2))     

["a", "time", "once", "upon"]

iex(6)> Enum.sort ["upon","once","a","time"], &(String.length(&1) > String.length(&2))

["time", "once", "upon", "a"]

I performed a quick search on the github repo and found nothing mentioning the stability of it. And even on this list I wasn't able to find the reasoning behind the current implementation. Needless to say "stabl" doesn't return anything on the documentation I linked above.

What are the considerations that made it not be a stable sort? Or is this a bug that merits a github issue?

[José Valim]

Good find. Please open up an issue, it must be at least discussed. Can you also please give it a try comparing to Erlang's :lists.sort/1 as well?

Thank you!

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Minten]

This might be related:

iex(1)> Enum.sort([1, 2, 1.0,2. 0])
[1, 1.0, 2, 2.0]
iex(2)> Enum.sort([2, 1.0, 2.0, 1])
[1, 1.0, 2.0, 2]

1 < 1.0 and 1.0 < 1 are both False (weirdness from the Erlang side), so
it's not the same as equal weight, but it might be caused by the same
underlying issue.

[Jamiel Almeida]

I believe > and < are both restrained in the "number" category.

On Dave Thomas' book (on beta) he describes:

number < atom < reference < function < port < pid < tuple < list < binary

But "number" might encompass all, integers and floats.

< and > return false because they are "==" even if they aren't "==="

iex(13)> 1 == 1.0 

true

iex(14)> 1 === 1.0

false

[José Valim]

Can this be possible because Enum.sort/2 only works with true and false values instead of :lt, :eq and :gt (or -1, 0, 1)? It has been a while since I implemented Enum.sort/2 and merge sort is not fresh in my memory. :)

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

[Jamiel Almeida]

I think stability doesn't have to do with what Peter mentioned actually.

Enum.sort/2 could be implemented with true/false or -1,0,1 of a <=> function regardless. 

--
Jamiel Almeida

[Gilbert Kennen]

On 04/11/14 02:59, José Valim wrote:
> Good find. Please open up an issue, it must be at least discussed. Can you
> also please give it a try comparing to Erlang's :lists.sort/1 as well?
>

Since it seems to have been lost, :lists.sort/2 gives the same result.
Erlang's sort implementation seems to actually maintain order just fine,
but can strictly reverse equal items if you aren't careful with how you
do your comparison. If you want the order to be preserved, equal terms
must evaluate to true (thus in this case, use <= or >=).

[José Valim]

Thanks Gilbert! I can verify this property also holds for Enum.sort/2. I will add the proper note to the docs.

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Lead Developer

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-talk+unsubscribe@googlegroups.com.