GNOME Bugzilla – Bug 508976
Does g_slist_sort preserve the order of equal elements?
Last modified: 2017-11-28 14:12:07 UTC
Please describe the problem: The documentation for g_slist_sort () at http://library.gnome.org/devel/glib/unstable/glib-Singly-Linked-Lists.html#g-slist-sort does not say what happens with two equal elements - is their original order preserved, does one of them disappear? Steps to reproduce: 1 Actual results: Expected results: Does this happen every time? Other information:
the order is unfortunately not preserved (i.e. the sorting is not "stable"). the documentation should outline this.
Created attachment 143791 [details] [review] Patch
By the way, g_list_sort() would also require a similar comment. Is that sorting algorithm stable?
Actually, it is currently implemented as a merge sort and thus is stable.
Review of attachment 143791 [details] [review]: Sorry, this has bitrotted for a bit too long: we no longer use DocBook in documentation comments, and the sorting algorithm actually is stable. I’ll provide an updated patch shortly.
See also: bug #531973, which fixed this for GList.
Created attachment 363822 [details] [review] gslist: Document that g_slist_sort() is stable Signed-off-by: Philip Withnall <withnall@endlessm.com>
Created attachment 363823 [details] [review] tests: Add tests to ensure g_[s]list_sort() are stable sorts Given that we guarantee it in the API… Signed-off-by: Philip Withnall <withnall@endlessm.com>
Review of attachment 363822 [details] [review]: :+1:
Review of attachment 363823 [details] [review]: :+1:
Attachment 363822 [details] pushed as 74cbd6c - gslist: Document that g_slist_sort() is stable Attachment 363823 [details] pushed as 2cd2671 - tests: Add tests to ensure g_[s]list_sort() are stable sorts