Snippet MergeSort

[Jesus4Lyf]

Without any previous interest in the topic or investigations, I believe that all the following are untrue:
>However, you can't sort all the things with radix sort. With radix sort you're more or less restricted to sorting (bounded) ints.
>I don't think JASS supports Radix sort, and even if, this is sorting for linked lists, MergeSort is the best.

I don't see why a radix sort algorithm couldn't automatically bound detect, including for floats with decimal places, and I don't see why MergeSort is better than Radix. And of course JASS supports Radix...

I don't really know why anyone bothers using sort algorithms which -aren't- Radix...

Post-thought: Ok, it might not be very efficient for reals, with automatic length detection... scrap that thought perhaps. But I do presume it to be the best alternative for anything integer based, and I would just convert reals to integers if they were distances, seeing as sorting based on the <0.9 amounts is really trivial.

 

[Dirac]

@J4L
MergeSort is better for linked lists, if you want a radix sort, code one for common number arrays.

Updated the system, found a way to accomplish what phyrex1an wanted without the use of function interfaces.
Added a new resource that combo's with it.

 

[Switch33]

Hey, can you provide some better instructions?(like what some demo code would look like) I'm not too familiar with text macros. I understand how to use them in some cases but these are a bit more advanced than the text macros I'm used to seeing.

I could definitely use this to have create a threat system since it'd be extremely efficient for the compare method.

 

[Dirac]

Silly me, looks like since the last update i removed the link to the post at the hive with the demo map included.
I re-added it, go check it out.
It has 2 demos:

• Pick the closest unit to a footman, move it around and it's closest unit will be pointed to
• Press Esc to generate random number lists and sort them

 

[Dirac]

Updated to v3.0.0
-For changelog visit the hive workshop

 

[Darthfett]

-For changelog visit the hive workshop

Why? I thought the resource was posted here as well?

 

[Dirac]

You're right.
v3.0.0 Changelog
-Removed the MERGE_SORT_EX textmacro
-The MERGE_SORT textmacro now takes two arguments
-Rewrote the documentation at the top of the script to explain how the new version works (Demo map included)

 

[phyrex1an]

Looks about as good as you can get it without using function interfaces. Are you sure that vjass compilers doesn't do specialization to remove the overhead of function interfaces? I guess you are sure

You can now sort a single list using different strategies, as long as the sort strategies are known to the one implementing the list. You can't take a list returned from some other library and sort it using your own comparator. I'm guessing it can't be done without breaking encapsulation (or using function interfaces...).

 

[Dirac]

You do can sort other struct lists, but it would require adding a third argument to the merge sort textmacro (the struct-to-be-sorted's name) which would replace all the "thistype" keywords in the code, it would be better if the user did it on it's own rather than doing that change

 

[Dirac]

v3.0.1
-Fixed it to work with the newest version of LinkedListModule (v2.2.0)

Also, some reasons why use MergeSort over other sorting algorithms
-MergeSort happens to be a very stable sorting method where the worst and best case happen to have the same complexity O(n log n) which is better than the best case of some of the other sorting algorithms and better than the best worst case among every other.
-The reason why its so stable is because of it's memory use (2n), compared to other sorting algorithms is high, but this doesn't matter in a w3 evironment.
-The algorithm used by this snippet can't be improved.