Qsort
Quoted 8 lines · Rafael J. Wysocki
Quoted 5 lines · Jesper Juhl
Quoted 1 line · Andi Kleen
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