How to sort a file fast?

[k_w_s_t_a_s]

I want to sort a file with records which is bigger than the memory available.The thing is that I want the file to be sorted depending on a field which only can take two values:0 and 1.
For example the file :

9423 John Pappas 0
2342 George Beckham 1
9423 Mary Lu 0
7123 Nick Zidane 1
1234 Ann Adams 1

should become :

7123 Nick Zidane 1
1234 Ann Adams 1
2342 George Beckham 1
9423 Mary Lu 0
9423 John Pappas 0

not caring about the order of all the records with 1's or all those with 0's in the sorted file.

Is there a better way than external merge sort that this could be done?Maybe in O(n) time?

[Magos]

The only pure sorting algorithm (as far as I know) that runs in O(n) is bucket sort, and that won't work since the keys aren't unique for the items.

You could however use a modified quick sort that runs in O(n).
Use two pointers to the items. Place them at both ends.

¤ Move the left pointer to the right until you find an item with a 1.
¤ Move the right pointer to the left until you find an item with a 0.
¤ If the left pointer is to the right of the right pointer, stop.
¤ Swap the items pointed out by the two pointers.
¤ Repeat.

This will cause all 0's to be placed to the left and all 1's to be placed at the right.

[kuphryn]

There are no elegant solutions for sorting data in files. One alternative is to use a temporary file and swap data. Another solution is file-mapping.

Kuphryn