# Worst case of Slowsort

## 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 true1) 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)\$$. 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 rules apply. The shortest code in bytes wins.

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

• Shouldn't T(1) = 1? Because otherwise, the entire sequence is just 0s T(2) = T(floor(1)) + T(ceil(1)) + T(1) = 0 + 0 + 0 = 0 Nov 29 '21 at 1:48
• @lyxal You missed +1 in the middle. Nov 29 '21 at 1:49
• Ah my bad - mobile didn't show the scroll bar on the bottom :p Nov 29 '21 at 1:50

-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. • You can do b<*" ". Also you can remove the space after the 0 – xnor Nov 29 '21 at 4:22 # 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! # Husk, 12 bytes ∫Θ¡§+→ȯ→←½;1 Try it online! Uses the idea of the Haskell answer. # 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. # 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) # Jelly, 15 bytes HḞ,ĊƊ;’ß€S‘µ0’? Try It Online! I don't think this is close to optimal. # Vyxal 2.4.1, 1918 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

# 05AB1E, 13 12 bytes

Implements the recurrence relation

0λND<‚;ï₅O+>

Try it online!

• Ah, of course. Decreasing N by 1 before halving.. Now that I see it, I can't believe I missed something so obvious. Nice answer! You can actually save an additional byte with 0λ>ND<‚;ï₅O+ (EDIT: which you've already figured out I see) Nov 29 '21 at 9:30

# Python 3, 42 bytes:

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

# 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.

# 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.

# 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).

# 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.