Results for test cases from file largeTests.txt Algorithm Type Size CPUTime (microseconds) ---------------------------- Merge r 503002 53585 Merge2 r 503002 52337 qsort r 503002 46527 Quick r 503002 37377 Quick2 r 503002 32050 QuickP1 r 503002 31818 QuickP2 r 503002 21525 QuickP4 r 503002 11858 QuickP8 r 503002 11235 QPbetter1 r 503002 49494 QPbetter2 r 503002 25426 QPbetter4 r 503002 14216 QPbetter8 r 503002 10889 ---------------------------- Merge r 1250001 149024 Merge2 r 1250001 146455 qsort r 1250001 122503 Quick r 1250001 97974 Quick2 r 1250001 84093 QuickP1 r 1250001 82810 QuickP2 r 1250001 52313 QuickP4 r 1250001 48151 QuickP8 r 1250001 31148 QPbetter1 r 1250001 133755 QPbetter2 r 1250001 68753 QPbetter4 r 1250001 44372 QPbetter8 r 1250001 29382 ---------------------------- Merge r 2250001 274731 Merge2 r 2250001 280177 qsort r 2250001 240608 Quick r 2250001 194499 Quick2 r 2250001 164709 QuickP1 r 2250001 164221 QuickP2 r 2250001 162383 QuickP4 r 2250001 68211 QuickP8 r 2250001 65437 QPbetter1 r 2250001 263018 QPbetter2 r 2250001 230928 QPbetter4 r 2250001 119295 QPbetter8 r 2250001 65831 ---------------------------- Merge r 4250001 559371 Merge2 r 4250001 537332 qsort r 4250001 454411 Quick r 4250001 365625 Quick2 r 4250001 313329 QuickP1 r 4250001 321208 QuickP2 r 4250001 295200 QuickP4 r 4250001 155785 QuickP8 r 4250001 108151 QPbetter1 r 4250001 506289 QPbetter2 r 4250001 443474 QPbetter4 r 4250001 209933 QPbetter8 r 4250001 133761 ---------------------------- Merge r10250001 1336389 Merge2 r10250001 1357960 qsort r10250001 1215754 Quick r10250001 927687 Quick2 r10250001 815692 QuickP1 r10250001 800815 QuickP2 r10250001 565735 QuickP4 r10250001 307243 QuickP8 r10250001 222238 QPbetter1 r10250001 1318170 QPbetter2 r10250001 972481 QPbetter4 r10250001 447228 QPbetter8 r10250001 299412 ---------------------------- Merge r20250001 2794995 Merge2 r20250001 2786753 qsort r20250001 2420377 Quick r20250001 1930481 Quick2 r20250001 1701966 QuickP1 r20250001 1677161 QuickP2 r20250001 944163 QuickP4 r20250001 799617 QuickP8 r20250001 498807 QPbetter1 r20250001 2734786 QPbetter2 r20250001 1886458 QPbetter4 r20250001 1170947 QPbetter8 r20250001 728292 ---------------------------- Merge r40250001 5596753 Merge2 r40250001 5576632 qsort r40250001 4921944 Quick r40250001 3910165 Quick2 r40250001 3450995 QuickP1 r40250001 3405949 QuickP2 r40250001 2006635 QuickP4 r40250001 1341165 QuickP8 r40250001 1122111 QPbetter1 r40250001 5585786 QPbetter2 r40250001 4504250 QPbetter4 r40250001 3228828 QPbetter8 r40250001 1759964 ---------------------------- Merge I 120800 7965 Merge2 I 120800 7346 qsort I 120800 3294 Quick I 120800 1241 Quick2 I 120800 821 QuickP1 I 120800 832 QuickP2 I 120800 559 QuickP4 I 120800 375 QuickP8 I 120800 435 QPbetter1 I 120800 3012 QPbetter2 I 120800 1579 QPbetter4 I 120800 974 QPbetter8 I 120800 4718 ---------------------------- Merge i 1004321 65647 Merge2 i 1004321 63731 qsort i 1004321 25631 Quick i 1004321 11621 Quick2 i 1004321 8532 QuickP1 i 1004321 7727 QuickP2 i 1004321 5062 QuickP4 i 1004321 4240 QuickP8 i 1004321 7917 QPbetter1 i 1004321 29357 QPbetter2 i 1004321 18812 QPbetter4 i 1004321 11184 QPbetter8 i 1004321 9763 ---------------------------- Merge i 2004321 137196 Merge2 i 2004321 136368 qsort i 2004321 55818 Quick i 2004321 25126 Quick2 i 2004321 17506 QuickP1 i 2004321 16589 QuickP2 i 2004321 16195 QuickP4 i 2004321 8306 QuickP8 i 2004321 6621 QPbetter1 i 2004321 65639 QPbetter2 i 2004321 52839 QPbetter4 i 2004321 27510 QPbetter8 i 2004321 20735 ---------------------------- Merge i 4004321 277087 Merge2 i 4004321 263571 qsort i 4004321 109063 Quick i 4004321 49915 Quick2 i 4004321 35094 QuickP1 i 4004321 34073 QuickP2 i 4004321 32223 QuickP4 i 4004321 16522 QuickP8 i 4004321 12927 QPbetter1 i 4004321 131498 QPbetter2 i 4004321 110679 QPbetter4 i 4004321 61388 QPbetter8 i 4004321 42681 ---------------------------- Merge O 1111111 71055 Merge2 O 1111111 70421 qsort O 1111111 37212 Quick O 1111111 16740 Quick2 O 1111111 10984 QuickP1 O 1111111 11293 QuickP2 O 1111111 11196 QuickP4 O 1111111 6606 QuickP8 O 1111111 6754 QPbetter1 O 1111111 34533 QPbetter2 O 1111111 26585 QPbetter4 O 1111111 14232 QPbetter8 O 1111111 10923 ---------------------------- Merge O 2111111 141309 Merge2 O 2111111 140638 qsort O 2111111 70576 Quick O 2111111 31842 Quick2 O 2111111 21509 QuickP1 O 2111111 21874 QuickP2 O 2111111 20774 QuickP4 O 2111111 11943 QuickP8 O 2111111 12320 QPbetter1 O 2111111 69997 QPbetter2 O 2111111 47916 QPbetter4 O 2111111 30876 QPbetter8 O 2111111 25874 ---------------------------- Merge O 4111111 272698 Merge2 O 4111111 280910 qsort O 4111111 144954 Quick O 4111111 62409 Quick2 O 4111111 44129 QuickP1 O 4111111 41201 QuickP2 O 4111111 26246 QuickP4 O 4111111 19013 QuickP8 O 4111111 21775 QPbetter1 O 4111111 141695 QPbetter2 O 4111111 107519 QPbetter4 O 4111111 69164 QPbetter8 O 4111111 49368 ---------------------------- Merge O 8111111 556677 Merge2 O 8111111 571152 qsort O 8111111 312787 Quick O 8111111 139674 Quick2 O 8111111 95085 QuickP1 O 8111111 90631 QuickP2 O 8111111 54739 QuickP4 O 8111111 36251 QuickP8 O 8111111 34764 QPbetter1 O 8111111 295148 QPbetter2 O 8111111 237703 QPbetter4 O 8111111 159938 QPbetter8 O 8111111 105214 ---------------------------- Merge O16211511 1108068 Merge2 O16211511 1110591 qsort O16211511 617450 Quick O16211511 262483 Quick2 O16211511 191087 QuickP1 O16211511 183180 QuickP2 O16211511 164792 QuickP4 O16211511 87471 QuickP8 O16211511 67687 QPbetter1 O16211511 620625 QPbetter2 O16211511 580988 QPbetter4 O16211511 354851 QPbetter8 O16211511 220235 ---------------------------- Merge m 100004 8965 Merge2 m 100004 9271 qsort m 100004 6861 Quick m 100004 8209 Quick2 m 100004 8190 QuickP1 m 100004 8550 QuickP2 m 100004 6581 QuickP4 m 100004 4135 QuickP8 m 100004 3238 QPbetter1 m 100004 8675 QPbetter2 m 100004 6371 QPbetter4 m 100004 2800 QPbetter8 m 100004 2100 ---------------------------- Merge m 100500 9035 Merge2 m 100500 9347 qsort m 100500 6910 Quick m 100500 8166 Quick2 m 100500 7685 QuickP1 m 100500 8002 QuickP2 m 100500 7143 QuickP4 m 100500 4383 QuickP8 m 100500 4812 QPbetter1 m 100500 8673 QPbetter2 m 100500 6377 QPbetter4 m 100500 2817 QPbetter8 m 100500 2193 ---------------------------- Merge m 100080 9863 Merge2 m 100080 10076 qsort m 100080 7709 Quick m 100080 6412 Quick2 m 100080 5268 QuickP1 m 100080 5241 QuickP2 m 100080 3065 QuickP4 m 100080 2032 QuickP8 m 100080 1947 QPbetter1 m 100080 8163 QPbetter2 m 100080 4077 QPbetter4 m 100080 2315 QPbetter8 m 100080 1941 ---------------------------- Merge m 100300 10320 Merge2 m 100300 10317 qsort m 100300 8122 Quick m 100300 6744 Quick2 m 100300 5463 QuickP1 m 100300 5494 QuickP2 m 100300 4592 QuickP4 m 100300 2538 QuickP8 m 100300 4126 QPbetter1 m 100300 8610 QPbetter2 m 100300 4358 QPbetter4 m 100300 2446 QPbetter8 m 100300 4282 ---------------------------- Merge m 1000081 113439 Merge2 m 1000081 114604 qsort m 1000081 94480 Quick m 1000081 75185 Quick2 m 1000081 65066 QuickP1 m 1000081 64322 QuickP2 m 1000081 34976 QuickP4 m 1000081 35738 QuickP8 m 1000081 21818 QPbetter1 m 1000081 100632 QPbetter2 m 1000081 52956 QPbetter4 m 1000081 32856 QPbetter8 m 1000081 23224 ---------------------------- Merge m 2000081 232086 Merge2 m 2000081 236297 qsort m 2000081 194855 Quick m 2000081 157752 Quick2 m 2000081 134439 QuickP1 m 2000081 131986 QuickP2 m 2000081 95428 QuickP4 m 2000081 57291 QuickP8 m 2000081 41448 QPbetter1 m 2000081 206988 QPbetter2 m 2000081 136146 QPbetter4 m 2000081 72966 QPbetter8 m 2000081 48929 ---------------------------- Merge m 4000081 470281 Merge2 m 4000081 479740 qsort m 4000081 400159 Quick m 4000081 330889 Quick2 m 4000081 275583 QuickP1 m 4000081 268307 QuickP2 m 4000081 149933 QuickP4 m 4000081 142220 QuickP8 m 4000081 81002 QPbetter1 m 4000081 418795 QPbetter2 m 4000081 270753 QPbetter4 m 4000081 171577 QPbetter8 m 4000081 100507 ---------------------------- Merge m 8000081 950546 Merge2 m 8000081 973314 qsort m 8000081 819468 Quick m 8000081 716536 Quick2 m 8000081 616141 QuickP1 m 8000081 603790 QuickP2 m 8000081 384665 QuickP4 m 8000081 286350 QuickP8 m 8000081 219383 QPbetter1 m 8000081 908279 QPbetter2 m 8000081 615922 QPbetter4 m 8000081 473920 QPbetter8 m 8000081 234495 ---------------------------- Merge c 100070 9251 Merge2 c 100070 9615 qsort c 100070 7133 Quick c 100070 7058 Quick2 c 100070 6049 QuickP1 c 100070 6093 QuickP2 c 100070 3929 QuickP4 c 100070 2249 QuickP8 c 100070 8550 QPbetter1 c 100070 8218 QPbetter2 c 100070 4184 QPbetter4 c 100070 2362 QPbetter8 c 100070 2101 ---------------------------- Merge c 1040500 112864 Merge2 c 1040500 115043 qsort c 1040500 88428 Quick c 1040500 95184 Quick2 c 1040500 93805 QuickP1 c 1040500 90072 QuickP2 c 1040500 52650 QuickP4 c 1040500 36325 QuickP8 c 1040500 30437 QPbetter1 c 1040500 107158 QPbetter2 c 1040500 59308 QPbetter4 c 1040500 33110 QPbetter8 c 1040500 31729 ---------------------------- Merge c 2040500 215619 Merge2 c 2040500 221156 qsort c 2040500 178497 Quick c 2040500 242045 Quick2 c 2040500 235740 QuickP1 c 2040500 254782 QuickP2 c 2040500 236713 QuickP4 c 2040500 164319 QuickP8 c 2040500 180145 QPbetter1 c 2040500 157266 QPbetter2 c 2040500 112197 QPbetter4 c 2040500 59019 QPbetter8 c 2040500 40035 ---------------------------- In Order Reversed Random Repeated Clumped Average Merge 121973 (4) 429961 (5) 1537835 (7) 225566 (8) 112578 (3) 575734 (27) Merge2 117754 (4) 434742 (5) 1533949 (7) 230370 (8) 115271 (3) 576709 (27) qsort 48451 (4) 236595 (5) 1346017 (7) 192320 (8) 91352 (3) 467093 (27) Quick 21975 (4) 102629 (5) 1066258 (7) 163736 (8) 114762 (3) 359964 (27) Quick2 15488 (4) 72558 (5) 937547 (7) 139729 (8) 111864 (3) 312630 (27) QuickP1 14805 (4) 69635 (5) 926283 (7) 136961 (8) 116982 (3) 308815 (27) QuickP2 13509 (4) 55549 (5) 578279 (7) 85797 (8) 97764 (3) 198496 (27) QuickP4 7360 (4) 32256 (5) 390290 (7) 66835 (8) 67631 (3) 135568 (27) QuickP8 6975 (4) 28660 (5) 294161 (7) 47221 (8) 73044 (3) 104712 (27) QPbetter1 57376 (4) 232399 (5) 1513042 (7) 208601 (8) 90880 (3) 515713 (27) QPbetter2 45977 (4) 200142 (5) 1161681 (7) 137120 (8) 58563 (3) 392186 (27) QPbetter4 25264 (4) 125812 (5) 747831 (7) 95212 (8) 31497 (3) 252634 (27) QPbetter8 19474 (4) 82322 (5) 432504 (7) 52208 (8) 24621 (3) 148465 (27)