Sorting algorithms II

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
Having found the optimal number of runs, I then varied the ‘orderedness’ of the generated sort lists. Orderedness corresponds to the chance that the number at index i is equal to i. If not, it is a random number. So an array with 0% orderedness is a completely random array, whereas one with 100% orderedness goes like 1, 2, 3, …, 100. I read that Q Sort doesn’t perform well on already quite ordered lists. I can verify that, except that when comparing to H Sort that moment is reached only around 98% orderedness, which is an almost completely ordered array. So no great advantage of H Sort so far…
• 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
Maybe better luck for H Sort when varying the array size? Indeed, H sort performs almost as well as Q Sort on arrays of size… 10. When increasing the array size, Q Sort quickly takes the lead. And then we run into the limitations of my Core i7 2.8 GHz laptop: sorting arrays of 10,000 numbers for 100,000 times took so much time I eventually gave up and killed the process.
• 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.