On Sun, 23 Jan 2005, Andi Kleen wrote: > > How about a shell sort? if the data is mostly sorted shell sort beats > > qsort lots of times, and since the data sets are often small in-kernel, > > shell sorts O(n^2) behaviour won't harm it too much, shell sort is also > > faster if the data is already completely sorted. Shell sort is certainly > > not the simplest algorithm around, but I think (without having done any > > tests) that it would probably do pretty well for in-kernel use... Then > > again, I've known to be wrong :) > > I like shell sort for small data sets too. And I agree it would be > appropiate for the kernel. > Even with large data sets that are mostly unsorted shell sorts performance is close to qsort, and there's an optimization that gives it O(n^(3/2)) runtime (IIRC), and another nice property is that it's iterative so it doesn't eat up stack space (as oposed to qsort which is recursive and eats stack like ****)... Yeah, I think shell sort would be good for the kernel.
-- Jesper Juhl - 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/
