##C - B-tree sort

This sorts randomNames.csv in about 5.8ms on my Core 2 T5500 @ 1.66GHz. My testing utility is here.

It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like trieing.

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Btree Btree;

static void btree_insert(Btree **btree, const char *key);
static void btree_emit_and_free(Btree *btree, const char ***out);

void sort(const char **strings, size_t count, const char **out)
{
    size_t i;
    Btree *tree = NULL;
    const char **out_start = out;
    
    for (i = 0; i < count; i++)
        btree_insert(&tree, strings[i]);
    
    btree_emit_and_free(tree, &out);
    
    assert(out - out_start == (ssize_t) count);
}

/*
 * Maximum (U) and minimum (L) number of *keys* per B-tree node.
 *
 * The maximum number of *branches* a B-tree may have is U+1 :
 *
 *       KEY   KEY
 *     /     |     \
 * branch  branch  branch
 */
#define U 20
#define L (U / 2)

struct Btree {
    /* Number of keys (rather than branches). */
    unsigned char count;
    
    /* 0 if node is a leaf, 1 if it has leaf children, etc. */
    unsigned char depth;
    
    const char *keys[U];
    
    /* Allocated to U+1 items if this is an internal node. */
    Btree *branches[];
};

static Btree *allocLeaf(void)
{
    return malloc(sizeof(Btree));
}

static Btree *allocInternal(void)
{
    return malloc(sizeof(Btree) + (U+1) * sizeof(Btree *));
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr);
static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr);
static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x);

static void btree_insert(Btree **btree, const char *key)
{
    if (*btree == NULL) {
        Btree *root = allocLeaf();
        root->count = 1;
        root->depth = 0;
        root->keys[0] = key;
        *btree = root;
    } else {
        const char *new_x;
        Btree *new_xr;
        
        if (insert(*btree, key, &new_x, &new_xr)) {
            Btree *root = allocInternal();
            root->count = 1;
            root->depth = (*btree)->depth + 1;
            root->keys[0] = new_x;
            root->branches[0] = *btree;
            root->branches[1] = new_xr;
            *btree = root;
        }
    }
}

static bool insert(Btree *node, const char *x,
                   const char **new_x, Btree **new_xr)
{
    unsigned int k = find_insertion_point(node->keys, node->count, x);
    Btree *xr;
    
    if (node->depth == 0)
        xr = NULL;
    else if (insert(node->branches[k], x, new_x, new_xr))
        x = *new_x, xr = *new_xr;
    else
        return false;
    
    return insert_item(node, k, x, xr, new_x, new_xr);
}

static bool insert_item(Btree *node, unsigned int k,
                        const char  *x,     Btree  *xr,
                        const char **new_x, Btree **new_xr)
{
    unsigned int i;
    bool internal = xr != NULL;
    
    if (node->count < U) {
        /* Enough case */
        for (i = node->count; i-- > k;)
            node->keys[i + 1] = node->keys[i];
        node->keys[k] = x;
        if (internal) {
            for (i = node->count + 1; i-- > k + 1;)
                node->branches[i + 1] = node->branches[i];
            node->branches[k + 1] = xr;
        }
        node->count++;
        return false;
    } else {
        Btree *r = internal ? allocInternal() : allocLeaf();
        
        node->count = L;
        r->count = L;
        r->depth = node->depth;
        
        if (k < L) {
            /* Left case */
            *new_x = node->keys[L - 1];
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            for (i = L - 1; i-- > k;)
                node->keys[i + 1] = node->keys[i];
            node->keys[k] = x;
            if (internal) {
                for (i = 0; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
                for (i = L; i-- > k + 1;)
                    node->branches[i + 1] = node->branches[i];
                node->branches[k + 1] = xr;
            }
        } else if (k == L) {
            /* Central case */
            *new_x = x;
            for (i = 0; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                r->branches[0] = xr;
                for (i = 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        } else {
            /* Right case */
            *new_x = node->keys[L];
            for (i = 0; i < k - L - 1; i++)
                r->keys[i] = node->keys[i + L + 1];
            r->keys[k - L - 1] = x;
            for (i = k - L; i < L; i++)
                r->keys[i] = node->keys[i + L];
            if (internal) {
                for (i = 0; i < k - L; i++)
                    r->branches[i] = node->branches[i + L + 1];
                r->branches[k - L] = xr;
                for (i = k - L + 1; i <= L; i++)
                    r->branches[i] = node->branches[i + L];
            }
        }
        
        *new_xr = r;
        return true;
    }
}

static unsigned int
find_insertion_point(const char *keys[], unsigned int count, const char *x)
{
    unsigned int start = 0;
    unsigned int middle;
    
    while (count) {
        middle = count >> 1;
        if (strcmp(x, keys[start + middle]) < 0) {
            count = middle;
        } else {
            start += middle + 1;
            count -= middle + 1;
        }
    }
    
    return start;
}

static void btree_emit_and_free(Btree *btree, const char ***out)
{
    unsigned int i;
    
    if (btree->depth == 0) {
        for (i = 0; i < btree->count; i++)
            *(*out)++ = btree->keys[i];
    } else {
        for (i = 0; i < btree->count; i++) {
            btree_emit_and_free(btree->branches[i], out);
            *(*out)++ = btree->keys[i];
        }
        btree_emit_and_free(btree->branches[btree->count], out);
    }
    
    free(btree);
}