Sorting linked lists

[David Kastrup <dak at gnu dot org>]

Hi,

I'd like to contribute a sorting routine for linked lists to glibc.
Regarding the complexity, it's a stable binary merge-sort needing only a
binary comparison operator <= or equivalent.

Which equivalence should I be rooting for?  The usual 3-way comparison
routine which will be applied then as

  if ((*compare)(a2, a1) < 0)
    { /* move a2 before a1 */ }
  else
    { /* keep a1 before a2 */ }

?  Note that as a stable sort, 0 and 1 will always be equivalent.  So it
would also be feasible to use

  if ((*less)(a2, a1))
    ...

and pass a less-pointer rather than a compare-pointer into the sort
function.

Apart from that, the core function gets passed a pointer to the list
head _and_ a count and will sort a sublist with the given number of
elements, returning a pointer to the tail of the result (consequently
a pointer to wherever the start of the next sublist ends up).

If you want to sort doubly-linked lists, the most efficient way is to
sort the forward list and just fix up the reverse list afterwards.

The glibc manual does not really show _any_ catering for linked lists as
a data structure, but one does not really need more of an identifying
trait than offsetof of the link field (would be nice to templatize on
that rather than have it as a parameter, but this is not C++) as long as
we are talking about in-memory lists.

So the question is _if_ one contributes a sorting routine, whether it
should be accompanied by other basic linked list algorithms.  Like one
calculating list length, and one merging two sublists (technically a
separate phase of a mergesort anyway, but since my implementation
flattens out the recursion of mergesort into iteration, the merge phase
is not accessible separately).

I think I proposed this about a decade ago on this list and offered a
C++ implemention for libstdc++ a few times as well.  It's obvious that
anything short of a completely finished patch is going to drop through
the floor with either project.

So what should be my next steps?  Presumably getting the copyright
assignment stuff done, right?

And on the technical side of the contribution, what should be in there
to make it a sensible part of glibc?

-- 
David Kastrup