Fixed (don't know about other languages yet)

But that's exactly the main feature of Timsort, taking advantage of having already sorted subsequences. If there are 2 sorted ranges, it's just an O(n) merge.

Because your solution is inefficient Python code, while sorted is a call to very optimized C function. I think even the best O(n) solution will at most be "nearly as good" as the top solution.

I've just run your solution against the reference with 1000 tests (in their current form). Yours one is 3.5 times slower...

Edit: and even after implementing your solution efficiently, it's a bit slower than the approach you're talking about.

Edit2: raised array length to fixed number of 1000 random integers, your solution is already 2 times slower.

Great to hear that you enjoyed it!

In fact all except tetranacci are zero padded and the firs four elements for every sequence are specified in that table.

Regards,

suic

The 'fib' pattern is the only one so the first four number have to be first four of Fibonacci sequence, meaning [0, 1, 1, 2] and not [0, 0, 0, 1] as assumed in the test. It is also unconsistent with the details page.

No. See rule 3: "The first four elements of the sequence are determined by the first abbreviation in the pattern (see the table below)." If you look carefully the first 4 element are zero padded

a - padding
b - first elements of the sequence

                      a      b
                    /---\  /---\
fibonacci: 0, 1 -->  0, 0,  0, 1
               b
         a  /-----\
padovan: 0, 1, 0, 0
                  b
            a  /-----\
tribonacci: 0, 0, 0, 1

etc.

table:

+------------+--------------+------------------------------------------+---------------------+
|  sequence  | abbreviation |         formula for n-th element         | first four elements |
+------------|--------------+------------------------------------------|---------------------|
| fibonacci  |     fib      | a[n] = a[n-1] + a[n-2]                   |     0, 0, 0, 1      |
....