On Fri, 31 May 2002, Alan Lawrence wrote: > well you need O(n) integers, but each one is O(log n) bits long.... Yes, but you are still sorting in O(n) time. The existence of a working O(n) algorithm does rather damage the chances of "proving" the hypothesis that you can't sort in less than O(n log n) time :-) James.