On Mon, 2005-01-24 at 21:43 -0300, Horst von Brand wrote: > AFAICS, this is just a badly implemented Shellsort (the 10/13 increment > sequence starting with the number of elements is probably not very good, > besides swapping stuff is inefficient (just juggling like Shellsort does > gives you almost a third less copies)). > > Have you found a proof for the O(n log n) claim?
"Why a Comb Sort is NOT a Shell Sort A shell sort completely sorts the data for each gap size. A comb sort takes a more optimistic approach and doesn't require data be completely sorted at a gap size. The comb sort assumes that out-of-order data will be cleaned-up by smaller gap sizes as the sort proceeds. " Reference: http://world.std.com/~jdveale/combsort.htm Another good reference: http://yagni.com/combsort/index.php Personally, i've used it in the past because of it's small size. With C++ templates you can have a copy of the routine generated for a specific datatype, thus skipping the costly function call used for each compare. With some C macro magic, i presume something similar can be done, for time-critical applications. Best regards, Eric St-Laurent - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/