4x repeats to concat 8 arrays with size 1 and 1 === === === === (3) = = // max 7 compares, 2x repeats to concat 4 arrays with size 2 and 2 === === ===== ===== ======= ======= (4) // max 15 compares, 1x repeats to concat 2 arrays with size 4 and 4 Formula extraction: n = 256 = 2^8 (array size in format 2^k, for simplify) On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1) On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128) On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128) | 1+2+4... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n is number of items, a1 is first item On = 8*n - 1 * (2^8 - 1) / (2 - 1) On = 8*n - (2^8 - 1) | 2^8 = n On = 8*n - (n - 1) On = (8-1)*n + 1 | 8 = ln(n)/ln(2) = ln(256)/ln(2) On = (ln(n)/ln(2) - 1) * n + 1 Example: n = 2^4 = 16, On ~= 3*n n = 2^8 = 256, On ~= 7*n n = 2^10 = 1.024, On ~= 9*n n = 2^20 = 1.048.576, On ~= 19*n Sorting a pre-sorted list If a list is already close to sorted, according to some measure of sortedness, the number of comparisons required to sort it can be smaller. An adaptive sort takes advantage of this "presortedness" and runs more quickly on nearly-sorted inputs, often while still maintaining an worst case time bound. An example is adaptive heap sort, a sorting algorithm based on Cartesian trees. It takes time , where is the average, over all values in the sequence, of the number of times the sequence jumps from below to above or vice versa. Notes References Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. . Section 5.3.1: Minimum-Comparison Sorting, pp. 180–197. Comparison_sorts Sorting algorithms