Sort benchmark results
All times are in milliseconds.
Proposed merge sort
=========================================
Int
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.705 1.779
descending 0.020 1.776
mostly sorted 0.029 2.904
shuffled 0.076 9.402
random (1...100) 0.075 7.245
random (full range) 0.078 9.186
new at end 0.024 1.849
pyramid 0.024 1.752
double pyramid 0.025 1.875
valley 0.024 1.900
double valley 0.025 1.987
many runs 0.048 2.090
all equal 0.022 1.754
=========================================
Large structs
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.053 3.865
descending 0.048 3.064
mostly sorted 0.058 10.505
shuffled 0.183 24.660
random (1...100) 0.178 23.190
random (full range) 0.193 24.672
new at end 0.027 3.487
pyramid 0.033 4.163
double pyramid 0.048 5.241
valley 0.039 4.468
double valley 0.043 5.416
many runs 0.118 7.438
all equal 0.050 2.708
=========================================
Reference types
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.089 8.284
descending 0.090 8.494
mostly sorted 0.153 46.613
shuffled 0.806 106.037
random (1...100) 0.850 103.682
random (full range) 0.814 100.645
new at end 0.124 12.975
pyramid 0.126 12.354
double pyramid 0.177 16.930
valley 0.125 12.762
double valley 0.176 16.018
many runs 0.460 25.072
all equal 0.089 8.168
=========================================
Long strings
=========================================
Shape 1000 100000
-----------------------------------------
ascending 2.843 185.441
descending 1.727 191.978
mostly sorted 3.838 902.216
shuffled 16.336 2138.377
random (1...100) 16.317 2052.829
random (full range) 16.722 2106.712
new at end 3.501 290.673
pyramid 3.482 278.084
double pyramid 5.649 377.398
valley 3.359 241.646
double valley 5.542 364.750
many runs 12.180 578.856
all equal 0.819 96.406
=========================================
NSObject subclasses
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.065 5.595
descending 0.071 5.634
mostly sorted 0.156 41.740
shuffled 0.817 98.991
random (1...100) 0.749 77.971
random (full range) 0.924 124.055
new at end 0.130 10.371
pyramid 0.086 8.378
double pyramid 0.125 11.997
valley 0.094 8.255
double valley 0.105 10.393
many runs 0.464 17.103
all equal 0.031 2.485
================================
Comparisons per 10,000 elements
================================
Shape Comparisons
--------------------------------
ascending 9999
descending 9999
mostly sorted 71921
shuffled 185386
random (1...100) 184876
random (full range) 184818
new at end 20837
pyramid 19998
double pyramid 32492
valley 19998
double valley 29993
many runs 55190
all equal 9999
Sort is stable in all cases
Current sort
=========================================
Int
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.017 2.261
descending 0.030 3.854
mostly sorted 0.037 9.317
shuffled 0.132 20.930
random (1...100) 0.098 12.551
random (full range) 0.132 21.122
new at end 0.075 8.362
pyramid 0.198 37.752
double pyramid 0.130 22.566
valley 0.177 36.718
double valley 0.154 19.902
many runs 0.093 14.136
all equal 0.045 5.362
=========================================
Large structs
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.025 4.349
descending 0.059 7.287
mostly sorted 0.058 13.950
shuffled 0.192 33.760
random (1...100) 0.158 18.996
random (full range) 0.194 33.256
new at end 0.120 15.255
pyramid 0.234 51.359
double pyramid 0.201 37.561
valley 0.231 50.923
double valley 0.179 34.701
many runs 0.145 26.565
all equal 0.056 13.142
=========================================
Reference types
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.179 32.385
descending 0.201 34.383
mostly sorted 0.269 52.983
shuffled 0.432 71.421
random (1...100) 0.334 93.449
random (full range) 0.453 74.121
new at end 0.375 54.909
pyramid 1.009 226.178
double pyramid 0.656 127.816
valley 0.944 218.427
double valley 0.566 106.047
many runs 0.345 62.191
all equal 0.578 86.671
=========================================
Long strings
=========================================
Shape 1000 100000
-----------------------------------------
ascending 8.079 1507.175
descending 8.063 1414.811
mostly sorted 7.497 1388.045
shuffled 8.430 1638.150
random (1...100) 6.952 2878.967
random (full range) 8.961 1688.647
new at end 7.850 1493.320
pyramid 9.961 1782.700
double pyramid 11.222 1823.674
valley 9.424 1736.871
double valley 8.612 1650.692
many runs 7.527 1570.025
all equal 15.470 2740.747
=========================================
NSObject subclasses
=========================================
Shape 1000 100000
-----------------------------------------
ascending 0.285 56.505
descending 0.307 57.989
mostly sorted 0.394 83.645
shuffled 0.582 96.893
random (1...100) 0.435 70.496
random (full range) 0.878 148.195
new at end 0.495 78.378
pyramid 1.304 274.418
double pyramid 0.912 182.413
valley 1.206 263.054
double valley 0.740 154.503
many runs 0.445 87.551
all equal 0.309 41.852
================================
Comparisons per 10,000 elements
================================
Shape Comparisons
--------------------------------
ascending 104538
descending 104556
mostly sorted 139940
shuffled 149398
random (1...100) 268503
random (full range) 149822
new at end 144282
pyramid 404245
double pyramid 277332
valley 383303
double valley 236871
many runs 143149
all equal 289591
Sort was unstable in: valley, double valley, many runs, all equal, pyramid, new at end, double pyramid, random (1...100), mostly sorted