Hi Neil! :-)

 NH> How does this sound:  do a QuickSort on the array (after it's 
 NH> been determined to all fit easily into memory).  QuickSort does an 
 NH> in-place sort.  The Bit-O QuickSort is n log n.
Quicksort has a worst-case of O(n^2), in the case of an already sorted
array. But your right, on random data it's O(n log n).

 NH> Then go once through the array eliminating the dupes.
Still O(n log n) in total, luckily.

 NH> The question then becomes: how does one 
 NH> eliminate the holes once all the duplicates are eliminated>
I thought you wanted to find out whether there are any duplicates at all?
Anyway, eliminating the holes would just be a memcpy, copying everything
above the hole down.

Ciao
Pascal

--- Msged/LNX 6.1.1