I second the suggested database approach. Using your favorite database (BerkeleyDB, SQLLite, MySQL, PostgresQL, Oracle, IBM UDB, etc), apply indices to the sort columns, and do a SELECT .. INTO OUTFILE, dump or equivalent.

I work on MySQL databases with single data files exceeding 0.5Gb every day, where indexed searched are more than fast enough for my purposes. Dumping whole tables of those sizes requires significant I/O, so be patient.