Content-Type: BBCode

For what it's worth, here's a C version of this program using the qsort() standard library function and a little bit of smart memory management to decrease the number of malloc() calls and increase spatial locality.  It also works with input files of an arbitrary number of lines, not hard coded like the C version in the original post.  The result is a program that is over twice as fast as the C++ quick sort version (with the same compiler optimization levels).

$ time ./sort-c++

real	0m2.650s
user	0m2.495s
sys	0m0.155s

$ time ./sort-c

real	0m1.139s
user	0m1.024s
sys	0m0.114s

Results above were with a larger input file, 633510 lines, and gcc version 4.1.2 20080704 (Red Hat 4.1.2-48).  I get similar results with gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5).


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

int strpcmp(const void *a, const void *b) {
	return strcmp(*(char const **)a, *(char const **)b);
}

int main() {
	FILE *fin = fopen("files.txt", "r");
	int c = 8192;
	int i = 0;
	int n = 0;
	char *buf = malloc(c);
	while(fgets(buf + i, c - i, fin)) {
		n++;
		i += strlen(buf + i) + 1;
		if(i + 512 > c) {
			c <<= 1;
			buf = realloc(buf, c);
		}
	}
	char **names = malloc(n * sizeof(char*));
	int m;
	i = 0;
	for(m = 0; m < n; ++m) {
		names[m] = buf + i;
		i += strlen(buf + i) + 1;
	}
	qsort(names, n, sizeof(char*), &strpcmp);
	FILE *fout = fopen("files.out", "w");
	for(i = 0; i < n; ++i) {
		fputs(names[i], fout);
	}
	return 0;
}