Generic insertion sort

Question

I implemented a generic insertion sort routine that can sort an array of any type. It's similar to the qsort function from the standard library. My goal it to optimize the code for readability above everything else, so I would appreciate any feedback.

void isort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
    for (size_t i = 1; i < nmemb; i++) {
        char *key = (char *)base + i * size;
        char key_copy[size];
        memcpy(key_copy, key, size);

        char *curr = NULL;
        for (curr = key; curr > base && compar(curr - size, key_copy) > 0; curr -= size) {
            memcpy(curr, curr - size, size);
        }

        memcpy(curr, key_copy, size);
    }
}

Example client code:

int cmp_int(const void *p, const void *q) {
    return *(int *)p - *(int *)q;
}

int main(void) {
    int arr[] = { 4, 2, 3, 0, 2, 5 };
    size_t nelem = sizeof(arr) / sizeof(arr[0]);
    isort(arr, nelem, sizeof(arr[0]), cmp_int);

    for (size_t i = 0; i < nelem; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

Answer 1

• Too many calls to memcpy. You don't need to memcpy individual elements. Once you found the place where key_copy should land, memmove the entire block of elements in one go.

• A mandatory no naked loops mantra.

  Every loop implements and algorithm, and therefore deserves a name. Make the inner loop a function.

• A mandatory insertion sort review.

  This implementation is suboptimal. At every iteration of an inner loop two conditions are tested: curr > base &and compar(curr - size, key_copy) > 0. You may get away with only one test per iteration (and perhaps less calls to compar).

  Compare the current key with the base key. If it is less, you know it shall land at the base; don't bother to compare anymore - just shift the entire block to the right. Otherwise, the base key serves as a natural sentinel, and you never hit a curr == base case.

All that said, consider

void isort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)) {
    for (size_t i = 1; i < nmemb; i++) {
        char * curr = (char *)base + i * size;
        char * insertion_point = base;

        if (compar(base, curr) <= 0) {
            insertion_point = find_insertion_point_unguarded(base, curr, compar, size);
        }

        char key_copy[size];
        memcpy(key_copy, curr, size);
        memmove(insertion_point + size, insertion_point, curr - insertion_point);
        memcpy(insertion_point, key_copy, size);
    }
}

An implementation of find_insertion_point_unguarded left as an exercise to the reader.