code doesn't compile, zip_sort isn't O(n log n)

[landfillbaby]

This code has a ton of typos. Have you actually tried compiling it? Where did you get the data for the tables? From @MusicTheorist's and my Java reimplementation of zip_sort it's obvious that it isn't O(n log n)

[landfillbaby]

I just assumed that if someone was going to post code online with tables of execution speed and computational complexity, and brag about it on Reddit (an unlisted YouTube video without my or more importantly the primary author/uploader's permission) and Wikipedia (link is to an editor pointing out that it's against the rules), they'd at least have code that compiles, let alone have accurate data.

[ceorron]

zip_sort is O(n log n) comparisons exactly. But in swaps/moves it is worse, much less than n^2 but far more than O(n log n). I have a calculation for the complexity of the number of swaps but have yet to write it up. I did note the difference in the documentation.

I did not realise posting this on reddit was against any rules. Sorry but thank you for doing this I'm not trying to brag just thankful at all.

I got the data for the tables from my own compiling version. If the one in my repo is not compiling it is because of any typos because I did copy/paste from my version.

Yeah I should really compile it and check that works before posting on github. I did check the version you did over and yes it is correct to my original version.

[ceorron]

Given your comments as I didn't realise the code didn't compile. I have made changes, the code now compiles with g++ on my machine.

Thanks

[MusicTheorist]

If the number of writes Zipsort makes to the array is far worse than O(n log n), then it isn't an O(n log n) sort. Binary insertion sort achieves O(n log n) comparisons, yet it is still an O(n^2) worst-case sort.

It took about 5,000,000 writes to sort an array of approximate size 16,000 (I know, vastly oversimplifying here), which is roughly 1.6 n log^2 n writes. Perhaps is it an O(n log^2 n) sort? That's not necessarily terrible, considering it can sort 2^14 random ints in under a fifth of a second using Java, but that still underperforms stable, in-place algorithms such as Block Merge Sort.

[MusicTheorist]

It's not against Reddit TOS to have posted the video, by the way. I was just confused why you shared it considering what I gave you was a private test video, and I was trying to ask if there were any bugs present...

[MusicTheorist]

Doing out a bit more math, I'm a bit more confident in my previous analysis. Zipsort is definitely not O(n^2 log n), let alone O(n^2 log^2 n), as 16,000 squared is 256 million, which far exceeds the 5 million writes Zipsort actually did as mentioned above. I'll bet your sort is O(n log^2 n) on average. In its best-case, it has O(n log n) performance, say on a reversed array. See if you can further break apart those merges between the buffers. The algorithm is an interesting idea; it just needs a bit of extra work!

[landfillbaby]

sorry i was so rude, by the way

[ceorron]

Thats OK, landfillbaby. You were no doubt angry at me posting the video without permission.

Take care.

[ceorron]

MusicTheorist, Thanks a lot for the excellent analysis of my algorithm you are most likely correct that the algorithm should be O(n log^2 n) in terms of complexity. I actually have a more in-depth analysis than that for the number of writes the algorithm makes. I also have inplace_merge_sort listed as O(n log n). This algorithm makes considerably more writes than zip_sort and may possibly more correctly labelled as n^2 based on the number of writes. So Big O, as I have it, should really only be used as an indication of the number of comparison not of the number of writes (or overall running time of an algorithm), which is why it is listed as O(n log n) so as not to confuse the issue. (If that makes sense)

I went back and re-thought my algorithm. I am possibly going to change zip_sort in the future with some optimisation that may well considerably reduce the number of writes the algorithm makes. But thinking about improvements to the algorithm I stumbled upon a similar idea, I have now added rotate_merge_sort and hybrid_rotate_merge_sort, these are different than the RotateMergeSort that you have in ArrayVisualizer which is a port of the one from GrailSort repo. https://github.com/MusicTheorist/ArrayVisualizer/blob/master/src/sorts/RotateMergeSort.java

I don't know if you would be interested in adding this rotate_merge_sort to ArrayVisualizer as I think it is a marked improvement over the one from the GrailSort repo.

[MusicTheorist]

You're welcome, but please note my analysis is not rigorous, and you would have to prove it mathematically!!

[ceorron]

Hey MusicTheorist & landfillbaby.

I did mention that I was going to update zip_sort/hybird_zip_sort to be more optimal in terms of the number of writes. Well today I published a revised version that manages the middle buffer slightly differently (new optimisation). If you would I'd really appreciate it if you could use this version as it is a little faster. Though only by a very small ammount.

Unless I have some amazing revelation about this algorithm this will be the last time I change it.

[MusicTheorist]

I'll check it out once my computer is back up and running!

[ceorron]

Well whenever that is, actually it might be worth waiting a bit. I have another version of zip_sort/hybird_zip_sort that I plan to publish tomorrow. So wait for that version before checking it out.

[ceorron]

I have just updated the code to have a new version of zip_sort, called new_zip_sort/hybrid_new_zip_sort. These are hugely faster than zip_sort/new_zip_sort but give up having constant stack space by default, however you can call them with constant stack space specified and optionally stable/unstable sort (stable option by default).