Thanks @bh,
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
Finally, I am able to pinpoint the reason why the implementation with the local function is not working, I examined many example library code, it seems what I implemented is legit, however, I could not make it work, finally, after many experiments, I found out the main reason is the usage of the primitive function calling, of course, I don't know enough to be able to provide a fix, however, I was able to modify the merge sort algorithm without calling the primitive sort provided by javascript, I am quite sure that you guys made lots of efforts of ensuring calling the primitive sort implementation is the best approach, now, I am still left wondering why the calling would result in the error.
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.)
If you compare Mergesort written in Snap! with the built-in Javascript sort, of course the latter will win because of large constant factors in the evaluation of Snap! code, until you get to really huge input lists, for which the order of growth outweighs the constant factors.
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.
Thanks @bh,
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
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.
