A376613 The binary expansion of a(n) tracks where the merge operations occurs in a Tim sort algorithm applied to n blocks.

0, 1, 5, 7, 53, 61, 119, 127, 1973, 2037, 4029, 4093, 16247, 16375, 32639, 32767, 1046453, 1048501, 2095093, 2097141, 8384445, 8388541, 16773117, 16777213, 134201207, 134217591, 268419063, 268435447, 1073708927, 1073741695, 2147450879, 2147483647, 137437902773

Offset: 1

Author

Darío Clavijo, Sep 29 2024

Keywords

• nonn
• base

Comments

Initial blocks for the Tim sort merges are usually found by checking for existing ordered runs, or insertion sort on a small number of elements; then here a(n) is how the merges proceed for n blocks.

Each adjacent pair of blocks are merged, and if the number of blocks is odd then one block is left unchanged; then repeat that process until just 1 block remains.

Each merge performed is encoded as a 1 bit, and a block left unchanged is encoded as a 0 bit.

The total number of 1 bits in a(n) is n-1, since each merge reduces the number of blocks by 1. In other words, A000120(a(n)) = n - 1.

The bitsize of a(n) is A233272(n)-1.

Examples

			For n = 10 a(10) = 2037 because:
Size | Block pair (l,m)(m,r) to merge | Left over block  | Encoding
-----+--------------------------------+------------------+-----------
   1 | ((0, 0), (0, 1))               |                  | 1
   1 | ((2, 2), (2, 3))               |                  | 11
   1 | ((4, 4), (4, 5))               |                  | 111
   1 | ((6, 6), (6, 7))               |                  | 1111
   1 | ((8, 8), (8, 9))               |                  | 11111
   2 | ((0, 1), (1, 3))               |                  | 111111
   2 | ((4, 5), (5, 7))               |                  | 1111111
   2 |                                | ((8, 9), (9, 9)) | 11111110
   4 | ((0, 3), (3, 7))               |                  | 111111101
   4 |                                | ((8, 9), (9, 9)) | 1111111010
   8 | ((0, 7), (7, 9))               |                  | 11111110101
11111110101 in base 10 is 2037.
For n=10, the merges performed on 1,...,10 begin with pairs of "blocks" of length 1 each,
  1  2  3  4  5  6  7  8  9  10
  \--/  \--/  \--/  \--/  \---/
   1     1     1     1      1    encoding
  [1 2] [3 4] [5 6] [7 8] [9 10]
  \---------/ \---------/
       1           1        0    encoding
Similarly on the resulting 3 blocks
  [1 2 3 4] [5 6 7 8] [9 10]
  \-----------------/
          1             0        encoding
Then a merge of the resulting 2 blocks to a single sorted block.
  [1 2 3 4 5 6 7 8] [9 10]
  \----------------------/
            1                    encoding
These encodings are then a(10) = binary 11111 110 10 1 = 2037.
		

Links

• Wikipedia, Timsort.
• Geeks for Geeks, Timsort.

Crossrefs

Cf. A000079, A000120, A077585, A233272.

Programs

Python

def a(n):
    if n == 1: return 0
    s, t, n1 = 1, 0, (n - 1)
    while s < n:
        d = s << 1
        for l in range(0, n, d):
            m,r = min(l - 1 + s, n1), min(l - 1 + d, n1)
            t = (t << 1) + int(m < r)
        s = d
    return t
print([a(n) for n in range (1,22)])

Formula

a(2^k) = A077585(k).