Egg on face time for me: I've claimed that the worst case for multipass pairing sort (Ralf Hinze named this 'jonssort', but I'm not keen on that - I'll call it mpp_sort here) had better worst case performance than merge sort. Unfortunately I hadn't worked out the worst case correctly. I had thought that > bad4merge n = take n (wcm m 1 m []) where > m = least_power_of_2_not_less_than n > wcm 0 l h acc = acc -- This never happens? > wcm 1 l h acc = h: acc > wcm 2 l h acc = h: l: acc > wcm n l h acc = wcm mid l h (wcm (n - mid) (l + mid - 1) (l + n - 2) acc) > where mid = n `div` 2 > > least_power_of_2_not_less_than n = lptbt n 1 > where lptbt n p = if p >= n > then p > else lptbt n (2*p) which generates one of the worst cases for merge was also worst for mpp_sort. Having thought about it a bit more I came up with > bad4mpp n = take n (wch m 1 1) where > m = least_power_of_2_not_less_than n > wch 0 _ _ = [] > wch 1 i s = [i] > wch n i s = (wch h (i) (2*s)) ++ (wch h (i+s) (2*s)) > where h = n `div` 2 Using versions of the sorts that count the number of comparisons, I get the following results: for bad4merge 1000, plain mergesort takes 8985 comparisons where mpp_sort takes 2769 but for bad4mpp 1000 mergesort takes 8983 but mpp_sort takes 12606 Back to the drawing board. I'd be interested in the results for these particular cases from other sorts, and also if someone could come up with real worst cases for each sort. Also interested to see closed versions of the above functions - my brain is too foggy to work them out myself. Jon -- Jon Fairbairn [EMAIL PROTECTED] 18 Kimberley Road [EMAIL PROTECTED] Cambridge CB4 1HH +44 1223 570179 (pm only, please)
