I haven't currently run any tests on it, but the performance of the method you suggest varies based on a few factors:
- How your C library implements qsort. C doesn't specify which sorting algorithm must be used, the choice is up to the implementation. The results may be significantly different if one implementation uses insertion sort and another uses quick sort.
- How you choose to allocate memory for the array and store it. This isn't likely to be significant performance-wise, but it's an extra problem to worry about.
And there's also the amount of data as well as the order it's presented in, which is likely to vary regardless of what algorithms/data structures you decide to use.
With that said, I decided to compare it against the following code:
and I had the following results (btree.c is the code I linked in my previous post, and array.c is the code pasted above):
#define MAX_LINES 6000000
static char *dup(const char *s)
if (!(r = malloc(strlen(s) + 1)))
return strcpy(r, s);
static int compar(const void *a, const void *b)
return strcmp(*(char *const *) a, *(char *const *) b);
static void print(char *const *s, size_t n)
static char *a[MAX_LINES];
size_t i = 0;
while (fgets(buf, sizeof buf, stdin) && i < sizeof a / sizeof a)
a[i++] = dup(buf);
qsort(a, i, sizeof a, compar);
Note that those were compiled without optimisations, and the file test is basically just the plaintext version of the C89 standard catted 360 times (5,129,640 lines, with each line < 80 characters.) The array version has shorter and perhaps simpler code, but it comes at the price of a fixed maximum number of lines. The times made by both programs are fairly good, at least in comparison with other methods, but I'd still say that a binary tree is the most practical choice in this case for its ease of implementation, insertion, and speed.
~ $ gcc -std=c99 -march=native -Wall -pedantic array.c -o array
~ $ gcc -std=c99 -march=native -Wall -pedantic btree.c -o btree
~ $ time ./array < test > tsta
~ $ time ./btree < test > tstb
~ $ diff tsta tstb
~ $ time ./array < test > /dev/null
~ $ time ./btree < test > /dev/null