[QUOTE=ultrafilter]
Loop 2 is the tricky part. It consists of some number of calls to merge, which we assume is O(n). If there a constant number of calls, the loop is O(n) and so’s the whole algorithm. But if there are n calls to merge, you’re looking at O(n[sup]2[/sup]).
[/QUOTE]
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
[QUOTE=Ellis Dee]
[QUOTE=groman]
Generating an index of blocks (which makes your storage requirement O(n log n) in the worst case, now that I think about it)
[/QUOTE]
I’m not sure I follow. The storage required by snake sort is 2.5n + 1. The mirror array requires the same space as the original, and the index array (by definition) cannot exceed half the items + 1, because the minimum number of elements in a block is two. (An additional initial border boundary of 0 is used to simplify the implementation, thus the +1.)
Of course, truth be told, I’m so ignorant of math that I don’t actually know what O(n log n) even means. What number does that produce for 50 elements? (Actual storage required for sorting 50 elements: 126)
[/QUOTE]
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).
