VB6: Sorting algorithms (sort array, sorting arrays)

[cbrow]

Hello Ellis Dee,
I have looked at Snake Sort and like it. I agree with what you say that it is about as fast as QuickSort on random data and much faster on sorted or partially sorted data. Other people call this sort a "Natural Merge Sort" but your implementation is about as fast as they get on randomly ordered data. It is possible to make it faster for partially sorted data but the added complexity will probably slow it when sorting random data.

I wouldn’t change it but there are a couple of things that are interesting to think about:

1. The buffer of ordered section details (lngIndex) only needs to be size logN. There is an elegant way to merge the sections in a binary pattern to achieve the exact same result as you have. It is marginally slower than your approach.

2. Consider the scenario when you have a lot of data that has been previously processed and is therefore in order. Then you get some new data added to the end that is not sorted. Say you look for your ordered sections and get:
Section 0: 1,000,000 elements in order
Section 1: 2 elements in reverse order
Section 2: 5 elements in order
Section 3: 7 elements in reverse order.

The binary approach that SnakeSort uses (and my suggestion above) would merge sections 0 & 1 (cost 1,000,002), then sections 2 and 3 (cost 12) and then the two results for a total cost of (1,000,002 + 12 + 1,000,014) = 2,000,028 operations.

A smarter approach would be to merge sections 1 and 2 (cost 7), then merge this with secion 3 (cost 14) and then merge this with section 0 (cost 1,000,014). The total cost of this is (7 + 14 + 1,000,014) = 1,000,035 operations.

It is most efficient to merge the smaller sections together first.

The problem is that these two ideas make the algorithm more complicated and therefore slower on random data. Unless you can think of anything.

[Ellis Dee]

I have looked at Snake Sort and like it. I agree with what you say that it is about as fast as QuickSort on random data and much faster on sorted or partially sorted data. Other people call this sort a "Natural Merge Sort"

Boooo. I thought I'd come up with an original idea, but googling does turn up references to and descriptions of natural mergesort, and it is indeed snake sort. Oh well.

Oddly, the only references I see to it are in messageboard discussions. There is no mention of this variation in the wikipedia entry for merge sort. (Wikipedia was my primary reference in this whole endeavor.) I also posted the snake sort algorithm along with a description on a heavily trafficked general interest board, claiming it as my own and asking if anyone had heard of anything similar. Nobody had; in fact, several people thought it was smooth sort. (ha!)

But after a day of mourning I'll go through and remove the self-credits in the Natural Mergesort algorithm, along with giving it its proper name. Again: Boooo!

As far as your points of consideration, particularly for an already-ordered list with new random elements. That situation calls for either an online algorithm like insertion sort or the unbelievably efficient smooth sort. That is what impresses me the most about smooth sort: it is an offline algorithm that handles "online data" as efficiently as any online algorithm. That's beyond impressive; it's pure genius.

I've also always been on the fence about what the term "nearly sorted" really means. If you use the utility attached to the OP and select "5% Shuffled", that techincally qualifies as "nearly sorted" because every element starts out near its final sorted position. And yet, this yields one of snake sort's worst performances, while smooth sort flies through it like greased lightning.

To really put it in perspective, select snake sort, smooth sort and insertion sort by clicking them, hit the Filter button and then the 5% Shuffled button. Watch smooth sort kick all kinds of ass. The higher your screen resolution the more obvious the difference will be. Even though this is Insertion sort's best case, smooth sort still wins.

[Ellis Dee]

2. Consider the scenario when you have a lot of data that has been previously processed and is therefore in order. Then you get some new data added to the end that is not sorted. Say you look for your ordered sections and get:
Section 0: 1,000,000 elements in order
Section 1: 2 elements in reverse order
Section 2: 5 elements in order
Section 3: 7 elements in reverse order.

In the previous post I claimed that insertion sort or smooth sort would be the better choice for such a scenario, but I appear to be mistaken. To see it in action, change the following code from the OrderArray function in basGraphical.bas:

        Case oeWeave
            ShellSort1 plngArray
            For i = iMax To iMax - 5 Step -1
                plngArray(i) = Int((iMax - iMin + 1) * Rnd) + iMin
            Next
'            WeaveArray plngArray, iMin, iMax

To get the full effect you really need to filter so that each algorithm fills the entire vertical space of the screen. Note that Weave order is called Thatched in the tooltip balloons on the toolbar.

Crazy as this seems, after a quick glance it would appear that even changing it to be one single out-of-place element at the end of the array -- the very definition of what an online algorithm is supposed to excel at -- the order of fastest to slowest seems to go snake sort, smooth sort, insertion sort.

[cbrow]

Hello Ellis Dee,
I have looked at Shear Sort and have read up on it. Don't expect this sort to work very fast because it is meant to run on N parallel processors. In any case I have found the problem:

There are three for loops that look like:
For j = 0 To Cols \ 2 - 1
or For j = 0 To Rows \ 2 - 1

When rows or columns are odd, these numbers need to round up like:
For j = 0 To CLng(Cols / 2) - 1
and For j = 0 To CLng(Rows / 2) - 1

or For j = 0 To (Cols + 1) \ 2 - 1
or For j = 0 To (Rows + 1) \ 2 - 1

The other thing is that this sort is especially bad if the number N is prime or if N has a large prime root.

Craig

[Ellis Dee]

I have looked at Shear Sort [...] I have found the problem

Sweet, that looks like a winner.

I can't thank you enough for all your help.