On Fri, 2004-06-25 at 10:55, Glenn Linderman wrote: > One trivial way to take advantage of the hint is to recall that the > lowly N-squared bubble sort (and variations) produces one high (or low) > value per pass, and that for small M and large N, that M*N is smaller > than N lg N. With regard to yesterday's post in which I'm thinking aloud, Considering bubbling or inserting the new, smaller element, based on expected average-case number of comparisons required, I think that bubbling will be better for M less than or equal to five. The reason is, binary search _always_ has to do lg(M-1) comparisons while bubbling can do anywhere from one to M-1 comparisons because bubbling stops when the new element has done like a mature executive and risen to the point where it can't rise any further, an expected number of (M-1)/2 comparisons. (M-1)/2 is equal to lg2(M-1) at M=5. -- david nicol "People used to be able to read my thoughts, but it doesn't appear to work any more. Should I eat less cheese?" -- Elizabeth Woods