# 几种简单的排序算法比较次数比较

## 1 说明

C 的 qsort 由于必须有函数指针, 比较是相对较大开销, 所以在数组较小, 且内 存足够时采用需要额外内存但比较次数最少的归并排序. C++ 采用的是 quicksort 和 heapsort 的杂交 introsort, 比较次数相对归并排序多一点, 但 对整数而言, 比较仅是减法, 受限于内存访问的时间, 估可以次要考虑.

## 2 sort comparisons table

Algo. Size time # comparisons/size # gets/size # sets/size introsort 2^5 2.29932e-06 5.27492 9.38623 4.00063 heapsort 2^5 2.70095e-06 5.18218 13.2291 8.45347 mergesort 2^5 2.37965e-06 3.79695 9.29695 6 quicksort 2^5 2.19414e-06 5.56079 8.359 2.83799 quicksort_nr 2^5 2.15747e-06 5.36925 8.23558 2.85841 cqsort 2^5 2.98512e-06 3.79623 NA NA combsort 2^5 2.41381e-06 8.80184 17.6123 3.36478 std::sort(iterator) 32 4.68653e-06 5.95218 13.9444 NA std::sort 32 1.65281e-06 5.94951 NA NA introsort 2^6 4.42774e-06 6.51571 11.0817 4.47673 heapsort 2^6 5.82915e-06 6.26207 15.305 9.46844 mergesort 2^6 4.97256e-06 4.76615 10.2662 6 quicksort 2^6 4.87501e-06 6.77834 10.0566 3.35011 quicksort_nr 2^6 4.76849e-06 6.60236 9.94205 3.3574 cqsort 2^6 6.40913e-06 4.76535 NA NA combsort 2^6 5.18118e-06 11.6094 23.2234 4.28761 std::sort(iterator) 64 3.99712e-06 7.11533 15.4967 NA std::sort 64 3.62354e-06 7.12488 NA NA introsort 2^7 1.00313e-05 7.76488 12.8293 4.99319 heapsort 2^7 1.28292e-05 7.30858 17.3461 10.4755 mergesort 2^7 1.94854e-05 5.74942 13.2494 8 quicksort 2^7 1.06718e-05 7.98551 11.737 3.83951 quicksort_nr 2^7 1.05284e-05 7.80488 11.614 3.8471 cqsort 2^7 1.41386e-05 5.74657 NA NA combsort 2^7 1.22646e-05 14.5126 29.0274 5.30448 std::sort(iterator) 128 8.65036e-06 8.32369 17.1383 NA std::sort 128 7.87806e-06 8.31551 NA NA introsort 2^8 2.16346e-05 8.96745 14.5286 5.49551 heapsort 2^8 2.79746e-05 8.33321 19.3682 11.4748 mergesort 2^8 2.38339e-05 6.74197 14.242 8 quicksort 2^8 2.26148e-05 9.21454 13.4375 4.31297 quicksort_nr 2^8 2.29063e-05 9.00217 13.2955 4.34143 cqsort 2^8 3.07402e-05 6.74541 NA NA combsort 2^8 2.71602e-05 17.383 34.7672 6.34737 std::sort(iterator) 256 1.99121e-05 9.54765 18.8368 NA std::sort 256 1.73477e-05 9.57421 NA NA introsort 2^9 4.58946e-05 10.1556 16.2247 6.01352 heapsort 2^9 6.01988e-05 9.35496 21.3922 12.4821 mergesort 2^9 5.17732e-05 7.73911 17.2391 1NA quicksort 2^9 4.92418e-05 10.3618 15.0615 4.8 quicksort_nr 2^9 4.81522e-05 10.1833 14.9512 4.81563 cqsort 2^9 6.54729e-05 7.74022 NA NA combsort 2^9 5.884e-05 20.3521 40.7047 7.38508 std::sort(iterator) 512 4.32935e-05 10.7954 20.6048 NA std::sort 512 3.68822e-05 10.7974 NA NA introsort 2^10 0.000100438 11.3582 17.9356 6.51449 heapsort 2^10 0.000128305 10.361 23.3974 13.4805 mergesort 2^10 0.000106804 8.73833 18.2383 10 quicksort 2^10 0.000104649 11.5757 16.7461 5.26775 quicksort_nr 2^10 0.000102984 11.4302 16.6564 5.27142 cqsort 2^10 0.000185398 8.73907 NA NA combsort 2^10 0.000144469 23.9508 47.9019 8.49806 std::sort(iterator) 1024 8.9258e-05 11.9546 22.1866 NA std::sort 1024 7.89147e-05 12.0618 NA NA introsort 2^11 0.000230655 12.5322 19.6955 7.09028 heapsort 2^11 0.000288267 11.3662 25.4025 14.4817 mergesort 2^11 0.000239689 9.7364 21.2364 12 quicksort 2^11 0.00024103 12.7323 18.3789 5.75391 quicksort_nr 2^11 0.000217546 12.5383 18.2607 5.76871 cqsort 2^11 0.000305481 9.737 NA NA combsort 2^11 0.000289749 27.0919 54.184 9.64027 std::sort(iterator) 2048 0.000190891 13.1735 23.8782 NA std::sort 2048 0.00016664 13.1915 NA NA introsort 2^12 0.000462502 13.8416 21.6096 7.6772 heapsort 2^12 0.000570066 12.37 27.405 15.4825 mergesort 2^12 0.000510409 10.7365 22.2365 12 quicksort 2^12 0.000469625 13.9459 20.0833 6.24193 quicksort_nr 2^12 0.00046391 13.706 19.9027 6.24634 cqsort 2^12 0.000642657 10.7388 NA NA combsort 2^12 0.000638999 30.2622 60.5245 10.6047 std::sort(iterator) 4096 0.000405341 14.4655 25.6454 NA std::sort 4096 0.000358723 14.6613 NA NA introsort 2^13 0.000944316 14.9803 23.2548 8.18111 heapsort 2^13 0.0012345 13.3728 29.4096 16.483 mergesort 2^13 0.00111294 11.7366 25.2366 14 quicksort 2^13 0.00100707 15.1234 21.7303 6.71223 quicksort_nr 2^13 0.000998065 14.8599 21.535 6.73174 cqsort 2^13 0.00133355 11.7354 NA NA combsort 2^13 0.00143582 33.8422 67.6845 11.7082 std::sort(iterator) 8192 0.000863686 15.7674 27.4121 NA std::sort 8192 0.00074625 15.6189 NA NA introsort 2^14 0.00210512 16.126 24.9677 8.75029 heapsort 2^14 0.00262052 14.3694 31.4035 17.4816 mergesort 2^14 0.00231299 12.7382 26.2382 14 quicksort 2^14 0.00242236 16.1358 23.2343 7.2082 quicksort_nr 2^14 0.00239414 16.1299 23.2688 7.187 cqsort 2^14 0.00295651 12.7369 NA NA combsort 2^14 0.00316426 37.0912 74.1825 12.864 std::sort(iterator) 16384 0.00181475 17.1119 29.2536 NA std::sort 16384 0.00160038 17.1486 NA NA introsort 2^15 0.00504923 17.3696 26.8373 9.35675 heapsort 2^15 0.00568175 15.3648 33.3989 18.474 mergesort 2^15 0.00549728 13.7331 29.2331 16 quicksort 2^15 0.00467777 17.7633 25.2896 7.6303 quicksort_nr 2^15 0.00500149 17.2662 24.8932 7.67592 cqsort 2^15 0.00653201 13.7351 NA NA combsort 2^15 0.0070073 40.2167 80.4334 13.9531 std::sort(iterator) 32768 0.00384778 18.3338 30.9398 NA std::sort 32768 0.00335026 17.9507 NA NA introsort 2^16 0.00969255 18.5172 28.5819 9.94678 heapsort 2^16 0.0119691 16.3619 35.3975 19.4703 mergesort 2^16 0.0105975 14.7329 30.2329 16 quicksort 2^16 0.00940704 18.3235 26.4023 8.18502 quicksort_nr 2^16 0.00956297 18.1066 26.2475 8.1935 cqsort 2^16 0.0129935 14.7351 NA NA combsort 2^16 0.0143045 43.2142 86.4284 15.0652 std::sort(iterator) 65536 0.0081985 19.5519 32.6143 NA std::sort 65536 0.0070591 19.4078 NA NA introsort 2^17 0.0198309 19.2521 29.6758 10.3184 heapsort 2^17 0.026468 17.3554 37.3895 20.462 mergesort 2^17 0.0243878 15.7346 33.2346 18 quicksort 2^17 0.024967 19.9184 28.4427 8.62446 quicksort_nr 2^17 0.0206831 19.6728 28.2809 8.6527 cqsort 2^17 0.028708 15.7364 NA NA combsort 2^17 0.031451 46.2132 92.4263 16.2224 std::sort(iterator) 131072 0.017206 20.7359 34.2805 NA std::sort 131072 0.0147529 20.7001 NA NA introsort 2^18 0.0428371 20.7763 31.9917 11.08 heapsort 2^18 0.060225 18.354 39.3878 21.461 mergesort 2^18 0.054204 16.7354 34.2354 18 quicksort 2^18 0.0449061 20.9323 29.9506 9.11972 quicksort_nr 2^18 0.0444071 20.7911 29.8584 9.11888 cqsort 2^18 0.0612371 16.7355 NA NA combsort 2^18 0.0704291 49.2127 98.4253 17.2837 std::sort(iterator) 262144 0.0369871 21.8056 35.8416 NA std::sort 262144 0.0335541 21.7911 NA NA introsort 2^19 0.10531 22.1166 33.9756 11.7039 heapsort 2^19 0.169231 19.354 41.3876 22.4603 mergesort 2^19 0.128936 17.7362 37.2362 20 quicksort 2^19 0.105645 22.1267 31.6042 9.58018 quicksort_nr 2^19 0.105005 22.234 31.7777 9.59514 cqsort 2^19 0.150182 17.7361 NA NA combsort 2^19 0.184128 52.2115 104.423 18.3483 std::sort(iterator) 524288 0.0942211 23.3306 37.815 NA std::sort 524288 0.0859551 24.1802 NA NA introsort 2^20 0.247764 23.4475 36.0754 12.4453 heapsort 2^20 0.442663 20.3545 43.3887 23.4609 mergesort 2^20 0.290556 18.736 38.236 20 quicksort 2^20 0.250626 23.2412 33.2074 10.0712 quicksort_nr 2^20 0.253931 23.3071 33.3181 10.0623 cqsort 2^20 0.344221 18.736 NA NA combsort 2^20 0.43086 56.2095 112.419 19.3904 std::sort(iterator) 1048576 0.230459 23.9554 38.9847 NA std::sort 1048576 0.20572 24.3193 NA NA introsort 2^21 0.554712 24.1748 37.1598 12.82 heapsort 2^21 1.07549 21.3544 45.3889 24.4613 mergesort 2^21 0.658452 19.7361 41.2361 22 quicksort 2^21 0.564909 24.3394 34.7983 10.5612 quicksort_nr 2^21 0.556773 24.0509 34.5808 10.582 cqsort 2^21 0.757419 19.7364 NA NA combsort 2^21 0.976948 59.2084 118.417 20.509 std::sort(iterator) 2097152 0.504422 25.5021 40.9916 NA std::sort 2097152 0.472489 25.5631 NA NA introsort 2^22 1.20346 25.5088 39.1727 13.4783 heapsort 2^22 2.48213 22.3542 47.3885 25.4608 mergesort 2^22 1.38512 20.7357 42.2357 22 quicksort 2^22 1.2088 25.6059 36.5275 11.0243 quicksort_nr 2^22 1.19371 25.8683 36.813 10.995 cqsort 2^22 1.5637 20.7359 NA NA combsort 2^22 2.02832 62.2124 124.425 21.6898 std::sort(iterator) 4194304 1.07368 26.5342 42.514 NA std::sort 4194304 0.977382 26.8222 NA NA introsort 2^23 2.48107 26.9948 41.4251 14.2166 heapsort 2^23 5.70184 23.3539 49.3881 26.4607 mergesort 2^23 2.93492 21.7357 45.2357 24 quicksort 2^23 2.53937 26.4896 37.9226 11.5348 quicksort_nr 2^23 2.52298 28.0309 39.3913 11.4106 cqsort 2^23 3.28481 21.7354 NA NA combsort 2^23 4.3994 66.2117 132.423 22.7599 std::sort(iterator) 8388608 2.23899 27.8882 44.3053 NA std::sort 8388608 2.05833 27.8466 NA NA introsort 2^24 5.28411 28.7927 44.2796 15.2239 heapsort 2^24 12.9595 24.3541 51.3883 27.4607 mergesort 2^24 5.96994 22.7357 46.2357 24 quicksort 2^24 5.19425 27.9376 39.8182 11.9814 quicksort_nr 2^24 5.23735 27.9376 39.8573 11.9697 cqsort 2^24 6.77857 22.7356 NA NA combsort 2^24 8.84291 69.2087 138.417 23.8582 std::sort(iterator) 16777216 4.70659 28.795 45.7217 NA std::sort 16777216 4.29975 29.2741 NA NA