GNOME Bugzilla – Bug 113203
Improve g_list_sort() implementation
Last modified: 2018-05-23 23:14:48 UTC
This function in glist.c isn't used: static GList* g_list_sort2 (GList *list, GCompareFunc compare_func) Let's get rid of it!
See: http://mail.gnome.org/archives/gtk-devel-list/2000-November/msg00112.html For an earlier unanswered query about the function. It seems to have been accidentally committed by me on December 2 1998. What the code looks like is a rewrite of the list sort code to be non-recursive and to reuse existing in-order runs in the code. I'm pretty darn positive that it isn't my code (too well commented, for one thing), though I can't dig up any reference in the GTK+ mailing lists, Google, or the old archives of GTK+ patches. While it does actually look like it contains good ideas and might be better than the current implementation, I suppose if reason to get of it, if we don't know where the code comes from, that's an excellent reason to get rid of it. So, I think it's OK to go ahead and remove it from glib-2-2 and HEAD.
* glib/glist.c: Remove unused function g_list_sort2 (bug #113203).
That's my code. g_list_sort has issues.
Re-opening... g_list_sort is a textbook implementation of merge sort. Unfortunately, it is a beginner's textbook. g_list_sort properties... * min/avg/worst time: O(n log n). * Stable [does not swap equal elements] * Essentially in-place [extra space needed independent of n] [Well, it uses O(log n) space, but that's ok.] g_list_sort2 properties... * avg/worst time: O(n log n). * min time: O(n) * Stable. * Not in-place. Linear min time for the near-sorted case is an important property, IMHO, often the difference between scaling and not scaling in practice. g_list_sort2 was a proof of concept I sent to Owen way back when. It could be better, and in fact it should be. The issue is that it is not in-place -- in fact this particular version can require quite a lot of extra memory. There are ways around that. Also it should not only accept increasing runs. Decreasing runs should be accepted (and inverted, of course). That way no runs would be shorter that two elements, except possibly one at the end. So there. I suggest... 1. We resintate g_list_sort2. 2. We improve it. 3. We have it replace g_list_sort (under that name).
Does anyone read this? I believe there's also a bug in the static function g_list_sort_real(). This is a merge sort algorithm which uses divide and conquare. It takes in 'list' and splits it into 'l1' and 'l2' then it does the recursion: return g_list_sort_merge (g_list_sort_real (list, compare_func, use_data, user_data), g_list_sort_real (l2, compare_func, use_data, user_data), compare_func, use_data, user_data); What? It calls one of the recursion with the original list instead of l1? I believe it should be: return g_list_sort_merge (g_list_sort_real (l1, compare_func, use_data, user_data), g_list_sort_real (l2, compare_func, use_data, user_data), compare_func, use_data, user_data); The sorting could also be further improved by checking size, and then break into an insertion sort for short lists. We could also consider quicksorting. -Øystein
"list" is right there. "l1" is just a one-element list at that point. We cannot use quick sort here as (1) it really requires random-access to the pivot element, or else it degenerates trivially and (2) it would make the sorting non-stable, i.e., equal elements might be swapped.
> "list" is right there. "l1" is just a one-element list at that point. Yes! Now I see. I also see that we can't use quick sort now. Do you think we might be able to improve things by checking the number of elements in the list (can be counted in the while-loop) and cut off to an insertion sort or selection sort for shorter lists?
Morten, would you mind attaching a patch of your old work?
I don't have that, but a "cvs diff -D... -D..." should hand it to you.
Created attachment 249450 [details] g_list_sort2 This is the g_list_sort2 function that was removed
-- GitLab Migration Automatic Message -- This bug has been migrated to GNOME's GitLab instance and has been closed from further activity. You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/8.