As posted a few days ago, I experimented a bit with a new sorting algorithm called H Sort. I built a simple testing framework in Java to see how well it performs compared to traditional Q Sort.
First I steadily increased the number of runs. I noticed that the average time it takes to do a sorting run decreases with the total number of runs. At first this seemed strange because the runs are unconnected, a new array of random numbers generated each run. Then I realized that this effect is probably due to more processing power and cores being allocated to the process when the number of runs increases. The average sorting times of the two algorithms begin to settle at 1,000 runs and become really stable at 100,000 runs.
- Times: 100 Orderedness: 0% Size: 100 Average time Q: 99,32 micros Average time H: 152,88 micros Factor H vs. Q: 1,54
- Times: 1000 Orderedness: 0% Size: 100 Average time Q: 9,40 micros Average time H: 37,18 micros Factor H vs. Q: 3,95
- Times: 10000 Orderedness: 0% Size: 100 Average time Q: 8,92 micros Average time H: 35,15 micros Factor H vs. Q: 3,94
- Times: 50000 Orderedness: 0% Size: 100 Average time Q: 8,81 micros Average time H: 33,52 micros Factor H vs. Q: 3,81
- Times: 100000 Orderedness: 0% Size: 100 Average time Q: 8,72 micros Average time H: 32,94 micros Factor H vs. Q: 3,78
- Times: 500000 Orderedness: 0% Size: 100 Average time Q: 8,87 micros Average time H: 33,52 micros Factor H vs. Q: 3,78
- Times: 1000000 Orderedness: 0% Size: 100 Average time Q: 8,77 micros Average time H: 33,15 micros Factor H vs. Q: 3,78
- Times: 100000 Orderedness: 0% Size: 100 Average time Q: 8,88 micros Average time H: 33,60 micros Factor H vs. Q: 3,78
- Times: 100000 Orderedness: 10% Size: 100 Average time Q: 8,70 micros Average time H: 33,43 micros Factor H vs. Q: 3,84
- Times: 100000 Orderedness: 20% Size: 100 Average time Q: 8,50 micros Average time H: 33,31 micros Factor H vs. Q: 3,92
- Times: 100000 Orderedness: 30% Size: 100 Average time Q: 8,28 micros Average time H: 33,07 micros Factor H vs. Q: 4,00
- Times: 100000 Orderedness: 40% Size: 100 Average time Q: 8,00 micros Average time H: 32,45 micros Factor H vs. Q: 4,05
- Times: 100000 Orderedness: 50% Size: 100 Average time Q: 7,76 micros Average time H: 31,75 micros Factor H vs. Q: 4,09
- Times: 100000 Orderedness: 60% Size: 100 Average time Q: 7,52 micros Average time H: 31,05 micros Factor H vs. Q: 4,13
- Times: 100000 Orderedness: 70% Size: 100 Average time Q: 7,29 micros Average time H: 30,12 micros Factor H vs. Q: 4,13
- Times: 100000 Orderedness: 80% Size: 100 Average time Q: 7,06 micros Average time H: 28,45 micros Factor H vs. Q: 4,03
- Times: 100000 Orderedness: 90% Size: 100 Average time Q: 7,07 micros Average time H: 23,88 micros Factor H vs. Q: 3,38
- Times: 100000 Orderedness: 95% Size: 100 Average time Q: 7,42 micros Average time H: 16,93 micros Factor H vs. Q: 2,28
- Times: 100000 Orderedness: 98% Size: 100 Average time Q: 8,15 micros Average time H: 8,85 micros Factor H vs. Q: 1,09
- Times: 100000 Orderedness: 99% Size: 100 Average time Q: 8,55 micros Average time H: 5,05 micros Factor H vs. Q: 0,59
- Times: 100000 Orderedness: 100% Size: 100 Average time Q: 9,08 micros Average time H: 0,50 micros Factor H vs. Q: 0,06
- Times: 100000 Orderedness: 50% Size: 10 Average time Q: 0,48 micros Average time H: 0,51 micros Factor H vs. Q: 1,08
- Times: 100000 Orderedness: 50% Size: 100 Average time Q: 7,74 micros Average time H: 31,75 micros Factor H vs. Q: 4,10
- Times: 100000 Orderedness: 50% Size: 500 Average time Q: 58,33 micros Average time H: 359,31 micros Factor H vs. Q: 6,16
- Times: 100000 Orderedness: 50% Size: 1000 Average time Q: 127,35 micros Average time H: 1323,50 micros Factor H vs. Q: 10,39
All in all we can say that H Sort is not a very good algorithm, which in no useful situation is able to outperform good old Q Sort. It was fun developing and testing it, but I’ll leave it at this. The project can be found on GitHub for those who want to try themselves and maybe improve the algorithm.