(factor): ratio of input size and limit Number of input elements is (limit)*(factor) Parallel tests performed only for (limit)*(factor) > 100 (data): boxed Integers - asc: presorted in ascending order - desc: presorted in descending order - rand: Random(1) - 10asc: concatenation of 10 groups presorted in ascending order - 10ad: concatenation of 10 groups presorted either in ascending or descending order - ascPairs: presorted in ascending order with pairs swapped (like 2, 1, 4, 3, 6, 5) - descPairs: presorted in descending order with pairs swapped (like 5, 6, 3, 4, 1, 2) Sequential Parallel (factor) (limit) (data) Original Patched Speedup Original Patched Speedup 1 2 asc 0.108 0.103 1.049 1 2 desc 0.118 0.107 1.103 1 10 asc 0.206 0.184 1.120 1 10 desc 0.251 0.209 1.201 1 10 rand 0.407 0.394 1.033 1 10 10asc 0.402 0.377 1.066 1 10 10ad 0.411 0.391 1.051 1 10 ascPairs 0.307 0.277 1.108 1 10 descPairs 0.459 0.457 1.004 1 100 asc 1.356 1.135 1.195 1 100 desc 1.505 1.265 1.190 1 100 rand 5.933 5.739 1.034 1 100 10asc 5.605 5.198 1.078 1 100 10ad 5.310 5.156 1.030 1 100 ascPairs 2.826 2.566 1.101 1 100 descPairs 5.430 5.429 1.000 1 1000 asc 10.728 9.508 1.128 20.423 32.573 0.627 1 1000 desc 11.983 11.226 1.067 22.429 34.748 0.645 1 1000 rand 120.228 120.854 0.995 135.786 147.050 0.923 1 1000 10asc 45.817 43.329 1.057 56.797 70.636 0.804 1 1000 10ad 43.504 43.741 0.995 50.122 64.863 0.773 1 1000 ascPairs 23.529 22.753 1.034 34.544 45.081 0.766 1 1000 descPairs 55.651 53.459 1.041 66.198 77.569 0.853 3 2 asc 0.135 0.139 0.971 3 2 desc 0.157 0.207 0.758 3 2 rand 0.209 0.238 0.878 3 2 10asc 0.211 0.244 0.865 3 2 10ad 0.248 0.270 0.919 3 2 ascPairs 0.194 0.163 1.190 3 2 descPairs 0.238 0.221 1.077 3 10 asc 0.316 0.346 0.913 3 10 desc 0.393 0.512 0.768 3 10 rand 1.263 1.072 1.178 3 10 10asc 1.216 1.046 1.163 3 10 10ad 1.188 1.069 1.111 3 10 ascPairs 0.701 0.554 1.265 3 10 descPairs 1.325 1.334 0.993 3 100 asc 2.590 2.010 1.289 14.203 16.792 0.846 3 100 desc 2.878 3.554 0.810 16.061 19.756 0.813 3 100 rand 21.502 17.831 1.206 38.321 37.979 1.009 3 100 10asc 10.870 9.746 1.115 25.657 28.787 0.891 3 100 10ad 11.771 9.813 1.200 25.547 28.140 0.908 3 100 ascPairs 7.033 4.981 1.412 21.709 22.861 0.950 3 100 descPairs 15.142 15.573 0.972 30.875 36.370 0.849 3 1000 asc 27.317 19.786 1.381 31.263 44.885 0.697 3 1000 desc 33.367 32.764 1.018 34.193 60.803 0.562 3 1000 rand 446.099 355.003 1.257 462.690 403.473 1.147 3 1000 10asc 137.829 97.915 1.408 151.171 132.451 1.141 3 1000 10ad 143.832 105.068 1.369 154.522 137.410 1.125 3 1000 ascPairs 59.503 45.973 1.294 67.036 71.500 0.938 3 1000 descPairs 152.294 159.650 0.954 164.885 192.363 0.857 5 2 asc 0.171 0.132 1.295 5 2 desc 0.188 0.318 0.591 5 2 rand 0.353 0.340 1.038 5 2 10asc 0.342 0.321 1.065 5 2 10ad 0.352 0.297 1.185 5 2 ascPairs 0.263 0.162 1.623 5 2 descPairs 0.410 0.323 1.269 5 10 asc 0.517 0.422 1.225 5 10 desc 0.553 0.875 0.632 5 10 rand 2.395 1.591 1.505 5 10 10asc 2.279 1.480 1.540 5 10 10ad 2.248 1.497 1.502 5 10 ascPairs 1.191 0.642 1.855 5 10 descPairs 2.408 2.162 1.114 5 100 asc 3.861 2.674 1.444 16.854 18.575 0.907 5 100 desc 4.264 6.060 0.704 18.189 23.077 0.788 5 100 rand 45.547 23.101 1.972 60.231 39.819 1.513 5 100 10asc 17.450 10.346 1.687 31.591 27.555 1.146 5 100 10ad 20.640 12.042 1.714 33.186 27.224 1.219 5 100 ascPairs 9.940 5.714 1.740 23.371 19.861 1.177 5 100 descPairs 24.938 27.060 0.922 39.349 35.635 1.104 5 1000 asc 31.411 23.498 1.337 32.605 45.637 0.714 5 1000 desc 39.625 53.311 0.743 42.975 68.312 0.629 5 1000 rand 771.045 484.399 1.592 795.736 389.586 2.043 5 1000 10asc 228.274 130.847 1.745 223.205 125.377 1.780 5 1000 10ad 248.484 126.410 1.966 254.796 126.215 2.019 5 1000 ascPairs 95.430 51.324 1.859 96.983 79.365 1.222 5 1000 descPairs 253.934 257.801 0.985 268.140 202.940 1.321 10 2 asc 0.244 0.193 1.264 10 2 desc 0.251 0.621 0.404 10 2 rand 0.747 0.431 1.733 10 2 10asc 0.740 0.436 1.697 10 2 10ad 0.927 0.483 1.919 10 2 ascPairs 0.432 0.224 1.929 10 2 descPairs 0.839 0.589 1.424 10 10 asc 0.823 0.761 1.081 10 10 desc 0.979 1.654 0.592 10 10 rand 5.446 2.185 2.492 10 10 10asc 4.955 1.736 2.854 10 10 10ad 4.774 1.805 2.645 10 10 ascPairs 2.260 0.973 2.323 10 10 descPairs 4.825 4.023 1.199 10 100 asc 6.029 4.180 1.442 19.821 18.749 1.057 10 100 desc 7.521 14.392 0.523 20.873 25.944 0.805 10 100 rand 117.235 35.182 3.332 133.508 49.460 2.699 10 100 10asc 41.759 14.445 2.891 55.492 27.677 2.005 10 100 10ad 40.310 15.771 2.556 53.042 27.720 1.913 10 100 ascPairs 19.046 7.556 2.521 33.159 23.194 1.430 10 100 descPairs 50.002 62.709 0.797 65.099 40.880 1.592 10 1000 asc 58.323 40.297 1.447 80.015 59.645 1.342 10 1000 desc 73.967 109.847 0.673 93.931 102.912 0.913 10 1000 rand 1689.001 670.721 2.518 617.022 450.417 1.370 10 1000 10asc 475.199 162.304 2.928 266.505 123.391 2.160 10 1000 10ad 475.067 160.741 2.955 257.912 136.447 1.890 10 1000 ascPairs 185.238 71.968 2.574 121.712 90.590 1.344 10 1000 descPairs 513.222 524.088 0.979 206.197 261.838 0.787 100 2 asc 1.622 1.267 1.280 8.767 8.875 0.988 100 2 desc 1.797 5.518 0.326 8.970 10.593 0.847 100 2 rand 12.452 1.958 6.360 21.189 10.476 2.023 100 2 10asc 10.187 2.005 5.081 18.210 9.832 1.852 100 2 10ad 9.070 1.723 5.264 17.617 10.428 1.689 100 2 ascPairs 4.392 0.803 5.469 12.643 8.674 1.458 100 2 descPairs 9.707 5.177 1.875 18.003 11.547 1.559 100 10 asc 5.601 3.815 1.468 15.312 17.399 0.880 100 10 desc 7.395 15.593 0.474 17.491 25.033 0.699 100 10 rand 117.176 8.225 14.246 131.263 26.608 4.933 100 10 10asc 41.469 6.548 6.333 49.034 19.103 2.567 100 10 10ad 38.053 8.396 4.532 46.043 22.753 2.024 100 10 ascPairs 19.131 4.050 4.724 30.128 18.739 1.608 100 10 descPairs 49.795 38.520 1.293 61.230 31.368 1.952 100 100 asc 53.658 37.418 1.434 79.908 34.175 2.338 100 100 desc 75.243 131.064 0.574 95.356 73.638 1.295 100 100 rand 1674.153 129.661 12.912 611.281 204.602 2.988 100 100 10asc 460.493 68.055 6.766 266.030 46.581 5.711 100 100 10ad 460.270 70.918 6.490 258.411 59.953 4.310 100 100 ascPairs 180.749 41.172 4.390 120.933 44.767 2.701 100 100 descPairs 508.987 515.939 0.987 210.252 179.506 1.171 100 1000 asc 560.396 395.981 1.415 444.182 140.324 3.165 100 1000 desc 898.444 1074.154 0.836 541.274 407.354 1.329 100 1000 rand 22204.936 1740.635 12.757 7896.966 2401.394 3.288 100 1000 10asc 4661.628 694.415 6.713 1828.939 287.577 6.360 100 1000 10ad 4622.516 692.163 6.678 1804.526 311.029 5.802 100 1000 ascPairs 2033.842 356.567 5.704 995.509 280.461 3.550 100 1000 descPairs 5282.371 5303.154 0.996 1990.423 1580.989 1.259 1000 2 asc 10.867 7.431 1.462 13.490 14.242 0.947 1000 2 desc 16.471 55.034 0.299 20.938 28.169 0.743 1000 2 rand 269.642 18.785 14.354 281.052 14.728 19.083 1000 2 10asc 93.252 17.347 5.376 95.576 13.743 6.955 1000 2 10ad 87.207 15.841 5.505 93.272 19.145 4.872 1000 2 ascPairs 36.775 7.515 4.894 40.348 12.795 3.153 1000 2 descPairs 100.892 51.364 1.964 104.364 30.446 3.428 1000 10 asc 54.616 37.073 1.473 84.903 26.770 3.172 1000 10 desc 71.621 159.458 0.449 90.003 64.981 1.385 1000 10 rand 1677.680 63.882 26.262 613.644 55.751 11.007 1000 10 10asc 463.989 62.712 7.399 262.910 29.839 8.811 1000 10 10ad 469.928 62.297 7.543 258.984 52.529 4.930 1000 10 ascPairs 183.687 38.065 4.826 112.708 29.657 3.800 1000 10 descPairs 505.995 416.277 1.216 203.633 139.096 1.464 1000 100 asc 522.010 321.971 1.621 440.428 125.758 3.502 1000 100 desc 884.982 1443.153 0.613 551.291 419.935 1.313 1000 100 rand 22337.412 739.261 30.216 7889.701 484.815 16.274 1000 100 10asc 4468.115 616.299 7.250 1805.079 154.564 11.679 1000 100 10ad 4602.854 612.500 7.515 1775.581 403.070 4.405 1000 100 ascPairs 2040.018 324.373 6.289 992.338 138.873 7.146 1000 100 descPairs 5256.420 5403.881 0.973 1984.404 1464.515 1.355 1000 1000 asc 29889.357 4431.718 6.744 28049.876 1421.037 19.739 1000 1000 desc 26774.054 10888.332 2.459 36761.758 3314.855 11.090 1000 1000 rand 402220.440 8307.931 48.414 145141.940 6144.936 23.620 1000 1000 10asc 67930.902 6558.386 10.358 75074.009 1684.778 44.560 1000 1000 10ad 68982.151 6596.692 10.457 37703.411 2186.259 17.246 1000 1000 ascPairs 33134.007 3768.392 8.793 71412.867 1745.983 40.901 1000 1000 descPairs 72553.605 53104.813 1.366 40469.652 15065.017 2.686