> On Sunday, January 23, 2005, Rafael J. Wysocki wrote: > > On Sunday, 23 of January 2005 06:05, Jesper Juhl wrote: > > > On Sun, 23 Jan 2005, Andi Kleen wrote: > > 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), > > Yes, there is.
After doing a small amount of research into this, according to the abstract at http://www.cs.princeton.edu/~rs/shell/paperF.pdf you can get O(n^(4/3)) with different increment sequences. (1, 8, 23, 77, 281 ...) So I guess the sort function could look something like this for XFS use (for reference only!): void shellsort(void *array, size_t total_elems, size_t size, int (*cmp)(const void *, const void *)) { size_t i, j; int k, h; register char *a = array; const int incs[3] = {23, 8, 1}; for (k = 0; k < 3; k++) { for (h = incs[k], i = h; i < total_elems; i++) { j = i; while (j >= h && cmp(a + (j-h) * size, a + j * size) > 0) { swap(a + j * size, a + (j-h) * size); j -= h; } } } } -- James Lamanna - 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/
