Timsort's runs
Timsort begins by cutting the array into runs and putting them on the stack one after another. Repeat this first part of the work and print the lengths of the runs in the order in which they go on the stack.
- The minimum run length. Let m = n and r = 0. While m ≥ 64: if m is odd, r = 1; then m is divided by 2 with integer division. At the end minrun = m + r. This is how CPython computed it up to version 3.14: for n < 64 minrun = n, otherwise minrun is from 32 to 64.
- A run. From the current position the longest piece is taken that either does not decrease (each next element is no less than the previous one) or strictly decreases. Which of the two is decided by the first two elements: if the second is less than the first, the piece is strictly decreasing. Timsort reverses a decreasing piece, but its length does not change.
- Extension. If a run is shorter than minrun, it is extended to minrun, or to the end of the array if that is closer, with the following elements, which Timsort inserts into it by insertion. The next run is looked for right after the extended one.
Input
The first line holds n (1 ≤ n ≤ 2·105), the second n integers from 1 to 109.
Output
On the first line, the number of runs k; on the second, their lengths separated by spaces.
In the first example n = 6 < 64, minrun = 6, and the whole array is one run, extended by insertion. In the second n = 133, minrun = 34. The first run is the numbers from 100 to 30, strictly decreasing, 71 of them; the next 30 equals the previous one, and the decrease is no longer strict. The second run is 30, 29, 28, only three, and it is extended to 34. The remainder gets 28.
Examples
Example 1
6 5 3 8 1 9 2
1 6
Example 2
133 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 30 29 28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
3 71 34 28
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Why must a decreasing run decrease strictly? What would happen to two equal elements if such a run were reversed?
2The idea
This is direct simulation, and all the difficulty lies in three rules. A non-decreasing run allows equal neighbours, but a decreasing one does not: it is reversed, and two equal elements would swap places on reversal, while Timsort is stable and does not do that. A short run is extended to minrun, and the next one is looked for from where the extension ended, not the natural run. And minrun is computed from the top six bits of n, plus one if any of the discarded bits was a one: then n/minrun is a power of two or slightly less, and the merges then go in even pairs.
3Walkthrough
Compute minrun. Walk through the array: from the current position lo, determine the direction by the first two elements and extend the run while it holds, strictly for decrease, non-strictly for increase. If the length is less than minrun, replace it with min(minrun, n − lo). Record the length and move to lo + length. The elements inside the extension do not matter: Timsort will sort them, but this does not affect the lengths of the following runs.
3+Solution
4Complexity
O(n): each position is looked at once.
5Common mistakes
- Non-strict decrease. The second example: the numbers 100…30, 30, 29, 28 look like one non-increasing run of 74 elements, but for Timsort it is 71 and then a new run.
- Looking for the next run after the natural one rather than after the extended one. The extension takes elements of the next run, and they no longer start a new one.
- minrun without the extra one. At n = 65 the top six bits give 32, but the discarded one makes minrun equal to 33.