## C - [B-tree][1] sort

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

It isn't the fastest algorithm for sorting this quantity of data, but I didn't feel like [trie][3]ing.

    #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);
    }


  [1]: http://en.wikipedia.org/wiki/B-tree
  [2]: https://gist.github.com/930486#file_gistfile1.c
  [3]: http://en.wikipedia.org/wiki/Trie