Skip to contentSkip to conversation

Qsort

PATCH James Lamanna 1 participant 1 message Jan 24, 2005

lore
Share & tools
lore
#0 lore raw
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