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);
}
LC_ALL=C sort randomNames.csv
takes about 20 milliseconds on my system. Any faster, and it would be nearly indistinguishable fromcat
. \$\endgroup\$