Hi Pascal.

20-May-04 00:28:40, Pascal Schmidt wrote to Neil Heller


 PS> 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
 NH>> an in-place sort.  The Bit-O QuickSort is n log n.

 PS> Quicksort has a worst-case of O(n^2), in the case of an already
 PS> sorted array. But your right, on random data it's O(n log n)

Most implementations of qsort() have code to handle that case better.

 PS> I thought you wanted to find out whether there are any duplicates
 PS> at all? Anyway, eliminating the holes would just be a memcpy,
 PS> copying everything above the hole down

that would be one O(n^2) way to do it. I like my O(n) way better.

 -=> Bye <=-
---