Asmus Freytag scripsit: > Normalization has mapping and reordering phases. The reordering is O(n > log(n)) where n is the length of a combining sequence. Realistically that's > a small number.
I tried sorting 100,000,000 runs of random bytes where each run has a randomly chosen length from 1 to 5 with a naive quicksort and a naive bubblesort. Although quicksort is O(N log N) and bubblesort is O(N^2), the bubblesort was just a hair faster, 220 seconds on my machine vs. 225 seconds, and the code is a lot shorter and easier to get right. A few experiments suggest that these results are linear in the number of runs, which is not surprising. Not invoking the sort algorithm when N = 1, the most trivial possible optimization hack, improves the advantages of bubblesort substantially, making the running time 206 seconds vs. 252 seconds. A 20% improvement, easily achieved, is not to be sneezed at. YMMV. -- I don't know half of you half as well John Cowan as I should like, and I like less than half [EMAIL PROTECTED] of you half as well as you deserve. http://www.ccil.org/~cowan --Bilbo http://www.reutershealth.com
