Mergesort: An analysis
From my previous implementation of Mergesort, I did some research on the overall comparisons.
Run | Expected | Comparisons | % | |
---|---|---|---|---|
a) | 3*1’000 | 9’976 | ||
b) | 4*10’000 | 133’616 | 13,39 * a) | |
c) | 5*100’000 | 1’668’928 | 12,49 * b) | -7,2% |
d) | 6*1’000’000 | 19’951’424 | 11,95 * c) | -4,5% |
e) | 7*10’000’000 | 233’222’784 | 11,68 * d) | -2,3% |
f) | 8*100’000’000 | 2’665’782’272 | 11,43 * e) | -2,1% |
Due to the 32bit memory addressing boundary ( possible addresses), I couldn’t check any larger lists. However you can clearly convince yourself that Mergesort is bounded in the number of comparisons to , with being a constant ~ 10 (see delta).