I finally got round to doing those experiments with your bubble-sort routine. My conclusion is that it usually behaves pretty well, a small factor worse than a good shellsort for sensible-sized datasets, and that it looks like it's asymptotically maybe a bit better than said good shellsort.
It is probably being slowed down a bit by the fact that my machine has incredibly bad floating-point performance, and I didn't try to remove the few floating-point operations in the routine. On the downside, it performs very badly for input data with the following structure: All the odd-numbered items are larger than all the even-numbered ones; each of those two sub-arrays (odd and even) have the same structure, and so recursively. On the upside, it does a very good job of noticing when you've given it data already sorted into order, and deals with that significantly faster than either shellsort or quicksort. Here are the figures, which you should take with a pinch of salt. The numbers are times in centiseconds. I can explain what the different datasets are if you want to know. Shellsort-2 is a really bad shellsort. Shellsort-3 is a pretty good one. Quick(Flat) is what I reckon is close to an optimal quicksort on my machine. Mergesort is, er, mergesort.1000 3000 10000 30000 100000 300000 FF Bubblesort 2.40 7.25 27.31 90.23 346.90 1156.72 Shellsort-2 1.62 7.95 42.51 201.42 1111.56 5739.68 Shellsort-3 0.92 4.04 14.50 56.77 245.88 956.87 Quick(Flat) 0.94 3.27 12.54 41.96 157.50 519.37 Mergesort 1.29 4.59 17.55 59.07 224.31 733.37
1000 3000 10000 30000 100000 300000 FF Bubblesort 0.40 1.54 5.94 20.18 75.31 250.01 Shellsort-2 0.70 2.78 11.01 37.49 142.25 472.35 Shellsort-3 0.43 1.71 6.71 23.00 87.72 292.23 Quick(Flat) 0.52 1.96 7.92 25.50 98.93 322.67 Mergesort 0.75 2.63 9.72 32.42 121.76 391.57
1000 3000 10000 30000 100000 300000 FF Bubblesort 1.41 4.27 15.38 49.73 187.79 631.06 Shellsort-2 0.84 3.21 12.68 42.54 163.35 542.24 Shellsort-3 0.60 2.26 9.03 31.30 114.85 380.19 Quick(Flat) 0.53 2.04 8.19 26.34 101.70 330.95 Mergesort 1.03 3.70 13.88 46.18 175.18 567.89
1000 3000 10000 30000 100000 300000 FF Bubblesort 1.61 4.80 17.50 59.84 227.54 780.09 Shellsort-2 0.93 3.68 15.26 54.94 220.27 768.09 Shellsort-3 0.64 2.40 9.59 33.54 130.20 443.95 Quick(Flat) 0.55 2.00 7.96 25.81 99.83 324.09 Mergesort 1.07 3.74 14.11 47.43 178.51 581.59
1000 3000 10000 30000 100000 300000 FF Bubblesort 0.96 3.14 12.58 48.42 166.43 618.89 Shellsort-2 0.79 3.15 12.78 45.00 178.28 621.14 Shellsort-3 0.54 2.08 8.33 29.04 112.50 382.81 Quick(Flat) 0.80 2.76 10.48 35.09 130.75 430.26 Mergesort 0.94 3.36 12.77 42.92 163.37 555.64
1000 3000 10000 30000 100000 300000 FF Bubblesort 1.83 5.58 21.62 75.56 301.03 1107.00 Shellsort-2 1.22 5.47 28.12 130.09 682.17 4170.05 Shellsort-3 0.71 2.80 11.99 45.04 191.73 720.25 Quick(Flat) 0.77 2.68 10.47 35.86 136.89 450.67 Mergesort 1.30 4.67 17.82 60.11 227.91 746.25
1000 3000 10000 30000 100000 300000 FF Bubblesort 1.94 5.88 22.91 802.39 277.30 3670.29 Shellsort-2 *** Shellsort-2 performs really badly here *** Shellsort-3 0.78 2.96 12.73 43.66 178.28 587.53 Quick(Flat) 0.97 3.47 13.07 44.01 167.44 533.93 Mergesort 1.33 4.73 18.11 60.88 229.45 754.79