Technically, the definitions everyone’s giving for “f(n) is O(g(n))” are really more for “f(n) is Theta(g(n))” or “f(n) ~ g(n)”, though the conflation is common enough (and Theta keys rare enough…) that one can’t complain too much.
But, if anyone cares about the pedantics:
“f(n) is O(g(n))” means that there is a constant which is an upper bound for f(n)/g(n) for sufficiently large n. I.e., the growth rate of f(n) is of less or equal order to that of g(n), in some sense.
“f(n) is Theta(g(n))” means that there are two positive constants which serve as upper and lower bounds on f(n)/g(n) for sufficiently large n. I.e., the growth rate of f(n) is of the same order as that of g(n), in some sense.
“f(n) ~ g(n)” means that f(n)/g(n) has limit 1 as n approaches infinity. I.e., the growth rate of f(n) is exactly the same as that of g(n), in some sense.
That last one isn’t very important in analyzing algorithms, of course, for all the usual reasons that one doesn’t pay attention to the specifics of constant factors. But distinguishing between big O and big Theta can be worthwhile.
Though it does have to take up stack space for its recursive calls, giving Theta(n) extra memory used in the worst case and Theta(log n) in the average case. [Or, with effort put into good pivot selection, or proper tail call optimization and some small cleverness about the ordering of recursive calls, Theta(log n) in the worst case]
It leads me to believe that you haven’t correctly identified the worst case. An algorithm can’t perform worse on a random case than on the worst case. The worst case is, by definition, the one that takes the longest to run. If your algorithm performs worse on a random case than on a particular case you’ve constructed, then you haven’t constructed the worst case.
Thanks, ultrafilter, I think I can follow most of that.
Some nitpicks:
My benchmark has two sections: graphical representation and time trials. The graphical representation displays visually how each algorithm functions, very similar to this page. The main difference is that you can change the size of the display area for any given algorithm, which helps identify scaling problems. For example, JSort isn’t particularly fast, though you’d never know that from the linked display where it’s the fastest. It just happens to be really efficient on lists of 50 items. Expanding it to even 70 shows a big slowdown compared to more advanced algorithms.
Anyway, the graphical display section counts the comparisons and exchanges and displays them for each algorithm upon completion, so it’s a trivial matter for me to come up with the actual numbers for any given run. The time trials ditch all that extra overhead and just measure speed of execution.
The worst case for snake sort is not descending order; descending order means that there’s only one pile, so that becomes optimally efficient. In fact, snake sort performs with the same efficiency as Counting sort on descending lists, which is quite impressive.
As for stability, I have included that information in the benchmark, but snake sort is decidedly unstable. Merge sort is the only stable algorithm I’ve found with any kind of decent running speed.
I’m not sure I follow. All I can tell you is that when I run snake sort on a thatched starting order – which will force it to create the maximum possible number of piles, and therefore be the worst case pretty much by definition – I get 1624 comparisons and 924 exchanges on a list of 231 items.
For a list of 231 items in random starting order, running five trials snake sort averages out to 1732 comparisons and 924 exchanges. (924 exchanges appears to be a constant, btw.) Therefore, I conclude that random ordering is the worst case.
Here’s the results for snake sort on 6 different starting orders on lists with 231 elements. “Camel hump” refers to the order described in the first example given in post 15. “Nearly sorted” refers to the second example in post 15:
Time is a rough approximation of a number independent of machine speed. An exchange takes roughly twice the time that comparisons do, so double the exchanges and add the comparisons to get the intial time. Multiple that by how quickly the computer can do comparisons, and that’s the ballpark number I’m looking for.
For comparison, quick sort’s results on the same list size in random order, average of five trials:
2421 comparisons, 485 exchanges (3391 time)
While quicksort is slightly faster, snake sort has the bonus of no O(n^2) worst case. (Which is camel hump for quicksort.)
Is there another starting order you can think of that I can throw at it to see if it performs worst than an average random case?
No, of course not.
I want to predict the number of comparisons and exchanges, not time. I can spend a half second or so clocking the computer speed and extrapolate out what the predicted time will be based on the predicted comparisons and exchanges.
The comparisons and exchanges are guaranteed to be constant across machines.
How do you reconcile this with the statement above that thatched order was the worst case by definition?
Of course, the worst case is, by definition, the case on which your algorithm performs the worst; if there is another case which causes your algorithm to take longer to run than the thatched starting order, then the thatched starting order is not the worst case.
I can’t. My best guess right now is that a thatched order will create an even number of equally sized piles, which resolve more efficiently than an odd number of piles of varying lengths.
When there is an odd number of piles, the last pile isn’t merged with anything. Instead, it is simply copied to the other array. This introduces inefficiency, especially as the number of piles decreases. Let’s say at some point there are 5 piles of length 1000, 1000, 1000, 999, 1. The first two piles are efficiently merged, the second two as well, then the last pile of 1 is straight copied. Now you have three piles of length 2000, 1999, 1. The first two are merged efficiently, and the third is copied. Now you have two piles: 3999 and 1. This is highly inefficient to merge together. Thatched probably has a much lower chance of this situation arising than a random starting order.
I originally wanted to snake the merging in both directions in order to reduce the chances that a single straggler pile of one element hangs on for a bunch of iterations, but that turned out to be far too compex than it was worth.
Ah, I misunderstood the algorithm. You’re right, it’s not stable. I’ll try for a pseudocode writeup later.
Now that I understand what it’s doing, I think the actual worst case is going to be an array of the form a[sub]1[/sub]b[sub]1[/sub]a[sub]2[/sub]b[sub]2[/sub]…a[sub]n[/sub]b[sub]n[/sub] that satisfies the following conditions:[ol]
[li]a[sub]1[/sub]a[sub]2[/sub]…a[sub]n[/sub] is either in sorted order or reverse sorted order.[/li][li]b[sub]1[/sub]b[sub]2[/sub]…b[sub]n[/sub] is either in sorted order or reverse sorted order.[/li][li]a[sub]n[/sub] < b[sub]1[/sub] or b[sub]n[/sub] < a[sub]1[/sub].[/li][/ol]That gives you eight cases to try out, so it shouldn’t take too horribly long.
That’s exactly what I thought, so I created it as one option for a starting order, which I named thatched. What I wanted to do was come up with the best and worst case starting orders for all algorithms as options in addition to a random shuffling. That way, using the graphical screen you can see exactly how any given algorithm’s Achilles heel is handled by the other 16 algorithms I implemented.
I’ll look into massaging the thatched “a” and “b” sequences to satisfy your suggestions in point 3 to see if they have any effect, but I suspect it won’t matter. I think the fact that all the intial piles end up with an equal number of cards makes the subsequent merge passes more efficient than the imbalanced pile merges you get with a random starting order. (See my previous post for more detail on this.)
I really do appreciate all the feedback from everyone, btw. Once I get the benchmark program done I’ll try and get an executable version posted somewhere so any of you who’d like to can download it and see snake sort in action.
As an example, resizing the graphical screen to get 13 elements, thatched order is defined as follows:
.1
…12
…3
…10
…5
…8
…7
…6
…9
…4
…11
…2
…13
This generates seven different starting piles, which (one would assume) is therefore the worst case scenario:
1, 12
3, 10
5, 8
7, 6
9, 4
11, 2
13
But using a thatched starting order consistently (I would go so far as to say always) results in fewer comparisons than a random starting order of the same length.
ETA: Let’s see if I can finish off the algorithm on this sample within the 5 minute edit window.
Mergesort is O(n) when given two lists of total length n. Each merging pass of Ellis Dee’s snakesort–if I understand it correctly–proceeds through the list of sorted sublists, of total length n, and merges them in pairs. So each merging pass is O(n). Because each pass basically halves the number of sublists, there are O(log n) passes, so all of the merging done in Loop 2 is O(n log n).
This is exactly the same analysis as used to prove that mergesort is O(n log n) in time; apart from list- and memory- management implementation details, ISTM that the only difference between snakesort and the classic mergesort is that snakesort starts with partially-sorted lists.
How large a difference this makes depends on the properties of the input. If the input is your “thatched” order, then you start out with blocksizes of 2 instead of 1, so you only manage to chop one pass off of mergesort. If the inputs contain, for whatever reason, large runs of sorted or reverse-sorted data, then you might be able to do much better. On random data (independent, identically-distributed samples from some random variable), runs will tend to be pretty short, so you won’t get much gain over mergesort.
Contra some of the posts here, it is not complete nonsense to ask (as you did) for estimates more exact than big-O notation. Some of these numbers–like runtime or number of elementary processor instructions–are architecture-dependent and not very meaningful for comparisons. But some higher-level counts, like the number of element-to-element comparisons, are fairly well-defined by the algorithm (and the list to be sorted, of course) and mostly processor-independent. Typically you consider some relatively expensive operation and view it as a black box or oracle, and then just count the number of oracle consultations required.
It is pretty easy to bound the number of comparisons required. Each merging pass needs at most n comparisons (each comparison processes at least one element onto a merged list), so mergesort in fact requires approximately n log[sub]2[/sub]n = n log n/log 2 comparisons in the worst case. Your Loop 2 can probably replace log[sub]2[/sub]n with log[sub]2[/sub]n - 1 in the thatched case, but of course you then have about n more comparisons from Loop 1, bringing the total up to pretty much the same as mergesort. (Wikipedia’s mergesort page provides some actual bounds, in case you want an actual upper bound on the number of comparisons required.)
I wouldn’t usually consider element copying or swapping to be expensive, though. For one thing, any modern language will have some referencing mechanism (e.g. reference counting, pointers, handles) which makes actual deep copying almost unnecessary. In the cases where you actually need to make a deep copy of a large object, you can always sort off some pointers and then make the deep copy from the sorted list (hence, always requiring only O(n) copies). groman didn’t come back to explain his statement
groman’s point (I think) is a sort of technical one, which is that if you want to allocate storage to hold a number between 0 and n-1, you need at least log[sub]2[/sub]n bits. So if you want to store n/2+1 offsets in the simplest way (each one stored as a number between 0 and n-1), you need (n/2+1)log[sub]2[/sub]n bits, which is O(n log n).
This is not really important in practice. If you’re sorting lists that are too large for indexing with a long, you’ve had to think about much harder problems than just indexing into the list. And anyway, if you really wanted to you could use a more complicated indexing method that is truly O(n), at the cost of a slightly longer runtime, but still O(n log n).
Essentially yes. One thing to remember is that many sorting algorithms are essentially the same as another one with a minor tweak like this. The relationship of snake sort to merge sort is exactly analagous to the relationship between smoothsort and heapsort.
Have you made any progress analyzing the worst-case?
I think it’s going to be something where sequential values are far apart from each other and the comparison test fails often, in a pattern that defeats your presort (2-size sequences). I can’t come up with a simple way to describe it, but for arrays, it may be easiest to give it in terms of decomposing a sorted list:
Split the sorted list in two by alternately placing the topmost value in the right and left array.
Recursively split the right and left arrays, until you have arrays of at most size 2.
A list of size 16 thus ends up looking like:
Your merging will reverse this process exactly. You can see that with each new sorted list, every successive value on the left list is higher than the value at the same rank on the right list. Thus you’ll have the maximum number of comparisons when merging the lists.
No I hadn’t, so I’m digging your idea. And thanks for the explanation; makes perfect sense and looks easy to code. I’ll post results as soon as I get it implemented.
Okay, I implemented it exactly as you describe, verifying that on a list of numbers 1-16, the initial ordering is the 8, 14, 4, 12, etc… ordering as shown in your chart.
First off, scaled up this is a visually cool starting order, so nice work. Any ideas on what to call it? I’m tentatively going with “sliced”, but am open to suggestions.
A quick test of all 17 algorithms on it shows typical results, with quicksort being fastest and snake sort being just a hair behind it in second place. On the 231 element test case – as used in the results upthread – the numbers are:
These results are clearly the worst I have seen snake sort post; the worst random case was, IIRC, 1786 comparisons and the standard 924 comparisons, so well freakin’ done!
Just to put it into context, quick sort’s worst case (camel hump) on 231 items results in:
Snake sort: 462 comparisons, 231 exchanges (924 time)
Quick sort: 14,029 comparisons, 339 exchanges (14,707 time)
So snake sort’s current worst case is just a hair off it’s performance on a random list, and on random lists it is roughly the same speed as quicksort.
More info on how this starting order impacts the faster algorithms. Kicking the screen resolution up to 1280x1024 (instead of my preferred 800x600) allows more lines to fit on screen. So for a list of 434 items in this new order:
You’d expect it to be about as good at random as at worst-case, since it’s similar to mergesort. Mergesort is O(nlogn) in both worst-case and random cases.
In fact, I think the comparisons to mergesort are most interesting. Are you comparing it with a mergesort that is just your ‘main loop’? It’d be interesting to try and see how it compares as the size of the average ‘in-order’ sequence changes.
As for the data mixing method, feel free to call it what you like. I might call it “logarithmic slicing” since it does log n slicing routines. ( I also think, but I’m not prepared to prove, that adjacent entries will end up at least log n apart from each other). I noticed I did make a mistake writing the numbers down, too - in my third and fourth columns 16 and 14 are switched.
