How do I optimize this merge sort I made?

I know the merge block Itself works, and it's fast, it's just the sorting algorithm i made with it that is slow.
It's apparently acting like O(N^2) and takes a few seconds to organize a 100000 items list. It's not as slow as selection sort and that stuff though.


And just in case:

A small adaptation that will make your code slightly faster (though IDK if it's noticeable), and shorter, is using the untitled script pic (48) predicate. Also, instead of deleting the first item of a list, you could raise the index by 1.

Instead of keep items you could use something like untitled script pic (49), it's much faster.

Anyway, a more elegant way of writing code (though not necessarily faster at execution time) is with these blocks:

untitled script pic (50)

I've decided. Do you think hybridizing it with selection for items under 10 or 5 length will optimize it?

I used the wikipedia pseudocode to make this.

It might. If you want to test how fast an algorithm is, try a block such as this one I adopted from @dardoro:

Programming tools DEVLAB script pic

(if the block to be tested is a reporter, use e.g. ignore (from the Iteration library) as a connector)

There are many pseudocode versions of merge sort at the relevant Wikipedia page.

For inspiration, here's one with lists (an adaptation from code by @bh, I think):

mergesort script pic (3)

mergesort script pic (4)

The comparator may be any predicate with 2 inputs. Using a variable comparator makes for somehwat slower execution BTW. But flexibility matters, too. :smirk:

Made my own ignore and duration block.




Definitely O(n log(n)), but slow O(n log(n)).
I'll optimize it using selection sort.

Well done!




Suprisingly, it performed worse! But the selection case is for 5 or less items.



If you really really want optimum speed for some application, other than experimenting with sorting algorithms as a goal for its own sake (which is interesting enough, IMO), Snap!'s built-in untitled script pic (47) block is very hard to beat.
In my experience there are two cases though where, for fastest processing, you'd want to write your own code (building on top of Snap!'s built-in sort):

  1. If you're only looking for the top x% of a list's items ("partial sorting");
  2. If you want to sort by a different key than by the item itself, in ascending order.


Whoa!
image
When was this feature added?

before i joined the snap forums

That last REPORT at the end of QUICK SORT will never happen (because the IF always reports), which is a good thing, because a recursive call with the same input (rather than a smaller input) would infinite loop!

I may be misremembering, especially if Wikipedia is telling you to use selection sort, but my impression was that the official quicksort algorithm uses insertion sort for small input lists.

The fastest (but ugliest) way to sort small lists is with explicit hard-coded comparisons, e.g.,


I think that's right, but I wouldn't swear to it. You'd have a similar procedure for lengths 0, 1, 2 (you already have those), 3 (above), 4, and 5. The one for length 3 does at most three comparisons, two if you're lucky. Note that there's no recursion in these small-list procedures, so if you have one for a length-five list, you'll never use the length-three procedure. You need the ones for lengths zero to four only in the case in which the original toplevel list is strictly smaller than length five.

What is that

I meant for Merge Sort.

Good thing to know, because i thought it would return "Reporter wouldn't Report"

I know, but (I should have said) Quicksort is a specific algorithm, for which someone got a PhD way back when, and it includes a whole bunch of optimizations, one of which is the one about using a simpler sort for small sublists. And I think it uses insertion sort, for a reason having to do with the fact that it performs better when the input data are already almost sorted. There isn't an official sorting algorithm for small sublists with mergesort because there isn't an official mergesort algorithm altogether. It's not that big a deal.

That would be if the script ended without doing a REPORT at all. You're expecting the computer to be really smart, to look at the input expression in the REPORT block and say "hey, wait a minute, you can't do a recursive call with the same input you were given." Computers aren't that smart. (People aren't that smart, either; in general it's theoretically impossible to predict infinite loops. You can find simple cases, but even in your example, the input expression is L (insert rant about sans serif fonts here) (insert rant about case-sensitive symbols here), not LIST, in the recursive call at the end. So it'd have to prove that L=LIST to know that this is an infinite recursion.

For all its wonderfulness, Wikipedia isn't going to teach you the habit of functional programming. If you apply DELETE to items in your input list, the caller of your sort function will be surprised that the original is gone. That is, the contract a reporter has with the user is that it doesn't change anything; it just reports a value. So if the user says SET [SORTED] TO (MERGE SORT (INCOMING)) they should be able to assume that they have two lists, INCOMING and SORTED, the first of which is still in its original order.