Worst case of Slowsort

Question

Background

Slowsort is an in-place, stable sorting algorithm that has worse-than-polynomial time complexity. The pseudocode for Slowsort looks like this:

procedure slowsort(A[], i, j)          // Sort array range A[i ... j] in-place.
    if i ≥ j then
        return
    m := floor( (i+j)/2 )
    slowsort(A, i, m)                  // (1.1)
    slowsort(A, m+1, j)                // (1.2)
    if A[j] < A[m] then
        swap A[j] , A[m]               // (1.3)
    slowsort(A, i, j-1)                // (2)

• (1.1) Sort the first half, recursively.
• (1.2) Sort the second half, recursively.
• (1.3) Find the maximum of the whole array by comparing the results of 1.1 and 1.2, and place it at the end of the list.
• (2) Sort the entire list (except for the maximum now at the end), recursively.

The recurrence relation of the worst-case time complexity (the number of swaps when the condition for (1.3) is always true¹) is:

$$ \begin{alignat}{5} T(1) &= 0 \\ T(n) &= T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + T\left(\left\lceil\frac{n}{2}\right\rceil\right) + 1 + T(n-1) \end{alignat} $$

The first 50 terms of the sequence are:

0, 1, 3, 6, 11, 18, 28, 41, 59, 82,
112, 149, 196, 253, 323, 406, 507, 626, 768, 933,
1128, 1353, 1615, 1914, 2260, 2653, 3103, 3610, 4187, 4834,
5564, 6377, 7291, 8306, 9440, 10693, 12088, 13625, 15327, 17194,
19256, 21513, 23995, 26702, 29671, 32902, 36432, 40261, 44436, 48957

This sequence seems to coincide with A178855.

A proof by @loopy wait (which gives rise to multiple alternative formulas):

Proof: start with A033485 (a(n) = a(n-1) + a(floor(n/2)), a(1) = 1) and verify that a(2n+1)-a(2n-1)=2a(n) (because a(2n+1) = a(2n) + a(n) = a(2n-1) + 2a(n)). Also verify that if n is even 2a(n)=a(n-1)+a(n+1). If we substitute b(n)=a(2n-1) we get b(n)-b(n-1)=b(floor(n/2))+b(ceil(n/2)) which is already similar to T. If we now set 2T+1=b we get back the recurrence defining T. As the initial terms also match this shows that T(n)=((A033485(2n-1)-1)/2 which (shifted by one) is also given as a formula for A178855.

Challenge

Evaluate the sequence \$T(n)\$. sequence default I/O applies; you can choose one of the following:

• Without input, output the entire sequence \$T(1), T(2), T(3), \cdots\$ infinitely
• Given \$n > 0\$, output \$T(n)\$ (corresponding to \$n\$th value under 1-indexing)
• Given \$n \ge 0\$, output \$T(n+1)\$ (corresponding to \$n\$th value under 0-indexing)
• Given \$n > 0\$, output the first \$n\$ terms, i.e. \$T(1), T(2), \cdots, T(n)\$

Standard code-golf rules apply. The shortest code in bytes wins.

---

¹ Don't ask me how, I don't know if it can actually happen.

Answer 1

Haskell, 31 bytes

-6 bytes thanks to @xnor.

a=s 0b
b=s 1$b<*"  "
s=scanl(+)

Try it online!

A178855 is the cumsum of A033485, while A033485 is the cumsum of 1, a(1), a(1), a(2), a(2), a(3), a(3), ..., where a is A033485 itself.

Answer 2

JavaScript (ES6), 31 bytes

Returns the \$n\$-th term, 0-indexed.

f=n=>n&&f(n>>1)+f(--n>>1)-~f(n)

Try it online!

Answer 3

Husk, 12 bytes

∫Θ¡§+→ȯ→←½;1

Try it online!

Uses the idea of the Haskell answer.

Answer 4

C (gcc), 34 bytes

f(n){n=n?f(n/2)+f(--n/2)-~f(n):0;}

Try it online!

Returns the \$0\$-indexed \$n^\text{th}\$ term.

Uses given formula.

Answer 5

05AB1E, 14 10 bytes

λN<2÷₅+}.¥

-4 bytes porting @alephalpha's Haskell answer and combining it with @ovs' 05AB1E approach of using n-1, so make sure to upvote both of them as well!

Outputs the infinite sequence.

Try it online.

Explanation:

λ        # Start a recursive environment,
         # to output the infinite sequence
         # Starting at a(0)=1 implicitly
         # Where every following a(n) is calculated by:
 N<      #  Push n-1
   2÷    #  Integer-divide it by 2
     ₅   #  Pop and push a((n-1)//2)
      +  #  Add it to the implicit previous item: a(n-1)+a((n-1)//2)
}        # After the recursive environment
 .¥      # Prepend 0 and get the cumulative sum of this list
         # (after which the infinite sequence is output implicitly)

Answer 6

Jelly, 15 bytes

HḞ,ĊƊ;’߀S‘µ0’?

Try It Online!

I don't think this is close to optimal.

Answer 7

Vyxal 2.4.1, 19 18 17 bytes

λċ[½₌⌈⌊x$xn‹xṠ›|0

Try it Online!

Of course just as I decided to make Ṡ no longer sum the stack, an edge case where it's needed pops up.

Explained

λċ[½₌⌈⌊x$xn‹xṠ›|0
λ                  # Start a monadic lambda taking argument n that:
 ċ[                #    if n != 1:
   ½₌⌈⌊             #        push the ceiling and floor of (n / 2)
      x$x          #        and call this lambda on both
         n‹x       #        then call this lambda on n - 1
            Ṡ›     #        finally, push the sum of the stack + 1
              |    #    else:
               0   #        return 0
                   # The lambda is automatically called on end of execution

Answer 8

05AB1E, 13 12 bytes

Implements the recurrence relation

0λND<‚;ï₅O+>

Try it online!

Answer 9

Python 3, 42 bytes:

f=lambda n:n and-~f(n//2)+f(~-n//2)+f(n-1)

Answer 10

Retina 0.8.2, 33 bytes

.+
$*
+`1(1*)(1*\1)
$1$2¶$1¶$2
¶¶

Try it online! Outputs the 0-indexed nth value. Explanation: Uses the recurrence relation given in the question.

.+
$*

Convert to unary.

+`1(1*)(1*\1)

Find the floor and ceiling of half of n.

$1$2¶$1¶$2

Replace n with n-1 and the above two values. This introduces two extra lines for each recurrence.

¶¶

Count half of the number of extra lines, which represents the number of 1s summed as part of the recurrence.

Answer 11

Rust, 56 bytes

fn f(n:i32)->i32{if n>0{f(n/2)-!f(!-n/2)+f(n-1)}else{0}}

Try it online!

Returns the \$n\$-th term, 0-indexed.

Answer 12

Charcoal, 20 bytes

ＦＮ⊞υ∨¬υ⁺⌈υ§υ⊘⊖ＬυＩ↨¹υ

Try it online! Link is to verbose version of code. Outputs the 0-indexed nth value. Explanation:

ＦＮ

Input n and loop that many times.

⊞υ∨¬υ⁺⌈υ§υ⊘⊖Ｌυ

Generate the next term of A033485, or 1 if there are no terms yet. (Annoyingly the formula for this sequence assumes 1-indexing.)

Ｉ↨¹υ

Sum the terms (using base 1 in case there are none).

Answer 13

Ruby, 38 ... 35 bytes

f=->n{n<2?n:f[n/2]-~f[n-=1]+f[n/2]}

Try it online!

Recursive version, as a function, returns nth value.

Ruby, 42 bytes

*r=a=b=c=0;loop{p c;a,b,*r=r+=[c+=a-~b]*4}

Try it online!

Non-recursive version, faster, prints whole list.