Here is the test case #3:
sort function with external compare (not local):
Here is the external weighted compare function:
Finally the non-working version using the local function:
The same testing case using the non-working sort function
Another question, is there any benchmark being done as to which implementation is faster: the lst_sort algorithm or the merge sort algorithm? I modified the merge sort in the final report block to recursively calling itself on the odd and even items, it seems working, I did not do extensive testing, but I think it is the right approach, now, I used my exact same implementation of sort with weighted function, but instead of calling the libary sort (which in turn calls the primitive lst_sort), I called my merge_sort function, everything works like a charm.
Mergesort is guaranteed to take O(n lg n) time, whereas the built in sort, which is almost certainly Quicksort, promises only to take O(n lg n) time on average, but can be up to O(n²) with unlucky inputs. (They use Quicksort rather than Mergesort because the former keeps the array in place, so it has better locality of reference and therefore better cache behavior.)
Mergesort is the algorithm of choice if what you have is a linked list rather than an array, because it works really well with recursion and doesn't mind having the data all over the place. Quicksort depends on being able to do arithmetic on memory addresses.
I appreciate your clarification on the comparison in terms of the speed. That makes a lot of sense.
Now, any final word on why call lst_sort with customized local compare function would fail, but the merge sort is happy to accept it?
No idea. Even harder to explain, I wrote
and then changed your procedure to
(to try to find out exactly where the error happens) and that works fine!
It also works if I use
(in the list utilities library where you found SORT) but not if I use
instead of LOG. So I think I'm happy to move this thread to the bug reports topic. :~/
Thanks @bh for your careful study and pinpoint the problem.
I am okay with you moving this thread to the bug reports section.