In this test each item was an array of 50 integers (iow. 200 bytes). Only the first integer was used for comparison. Thus in this test comparison is very fast but copying is slow.
The array of 1 million items was skipped because it was extremely slow to test.
In order to better compare the results with the previous strings test, both charts are shown in each case (strings test first, array test below it).
Insertion sort is not as much penalized as with the strings case, but still somewhat. Insertion sort probably makes more comparisons than copying (in relation to the comparisons/copying ratio of the other algorithms).
Except for the vanilla quicksort, all the others seem to behave very similarly to the strings test.
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Insert. | 2567 | 2670 | 418 | 517 | 4704 | 4827 | 2567 | 2670 |
| Shell | 767 | 1076 | 463 | 747 | 731 | 1092 | 767 | 1076 |
| Heap | 1027 | 1743 | 1069 | 1882 | 957 | 1558 | 1027 | 1743 |
| Merge | 558 | 800 | 470 | 800 | 424 | 800 | 558 | 800 |
| Quick | 1062 | 475 | 2809 | 241 | 2052 | 335 | 1062 | 475 |
| Quick2 | 783 | 724 | 691 | 393 | 599 | 487 | 783 | 724 |
A notable difference compared to the previous strings test can be seen with the vanilla quicksort, which in this case doesn't show signs of difficulty. Also merge sort seems surprisingly slower to the others in the arrays test.
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Shell | 101380 | 136567 | 76338 | 109893 | 81473 | 118792 | 67960 | 101361 |
| Heap | 107688 | 171316 | 109624 | 177665 | 103760 | 161278 | 111987 | 181247 |
| Merge | 56824 | 70000 | 51721 | 70000 | 51461 | 70000 | 34610 | 70000 |
| Quick | 95298 | 42894 | 336123 | 22098 | 215449 | 31199 | 1034091 | 27139 |
| Quick2 | 74281 | 56372 | 81006 | 32104 | 81059 | 38236 | 130804 | 33511 |
Again, quicksort handles this case better (except for the expected
"random end" pathological case) for some reason. The optimized quicksort
and even std::sort show the same problematic trend with
the "random end" case, although slightly less pronouncedly.
| Random | Almost sortd | Almost rev. | Random end | |||||
|---|---|---|---|---|---|---|---|---|
| Alg. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. | Comp. | Assig. |
| Shell | 3895921 | 4892488 | 2883376 | 3843683 | 2928766 | 3956272 | 1644643 | 2600399 |
| Heap | 3019596 | 4724828 | 3024825 | 4792736 | 2937903 | 4519024 | 3132332 | 4973720 |
| Merge | 1566495 | 1800000 | 1464797 | 1800000 | 1463588 | 1800000 | 879322 | 1800000 |
| Quick | 2551984 | 1153577 | 9853078 | 577498 | 6044543 | 848086 | - | - |
| Quick2 | 2022265 | 1432913 | 2145137 | 772913 | 2191912 | 906267 | 4813088 | 554475 |
Shell sort seems to be again just slightly better than heap sort.
A bit surprisingly the vanilla quicksort handles this case much better than the strings case.
Merge sort clearly loses its edge when copying is slow. The compare/copying ratio of merge sort seems to put it at an disadvantage compared to when comparison is slow and copying fast.