# Bottom-up well-balanced mergesort

If you implement mergesort top-down you can always split the input of length $$n$$ into one of length $$\lfloor n / 2\rfloor$$ and one of length $$\lceil n / 2 \rceil$$. This ensures that all merges are always well-balanced: the left and right inputs differ in length by at most 1.

Is there a way of achieving this property in a bottom-up stable mergesort (that is, only merging adjacent subarrays) using some clever arithmetic?

It's possible of course if you use a stack and effectively simulate the top-down algorithm, but what if you were limited to $$O(1)$$ memory for computing the merge indices?

To abstract away the mergesort we can also state the problem as such: given $$O(1)$$ memory and a number $$n$$, generate a series of triples $$(i, j, k)$$ such that:

• for each triple we have $$0 \leq i < j < k \leq n$$,
• for each triple we have $$|(j - i) - (k - j)| \leq 1$$,
• the last triple is $$(0, x, n)$$ for some $$x$$,
• if $$(i, j, x)$$ is in the list and $$j - i > 1$$, then $$(i, y, j)$$ must precede it for some $$y$$,
• if $$(x, j, k)$$ is in the list and $$k - j > 1$$, then $$(j, y, k)$$ must precede it for some $$y$$.

If the above constraints are met calling $$\operatorname{merge}(A[i..j], A[j..k])$$ for each triple would sort $$A[0..n]$$, while being a well-balanced mergesort.

• It seems that A110316 is of interest here, which I found by counting the number of possible solutions per $n$.
– orlp
Mar 12 at 21:05
• How would you merge $A[i..j]$ and $A[j..k]$ in $\mathcal{O}(1)$ space? In-place mergesort is possible, but it requires to create unbalanced subarrays. Mar 12 at 21:47
• @Nathaniel You may assume $\operatorname{merge}$ is a black-box operator whose memory budget is none of your concern. I'm just interested if the sequence of indices itself could be generated without extra memory/a recursion stack.
– orlp
Mar 12 at 22:02
• Noted. Also, you talk about a list of triples, but in order to do it in $\mathcal{O}(1)$, I suppose that you would like a generator rather than a list? Mar 12 at 22:06
• @Nathaniel Sure, I mean a series in the logical sense, not in a physical sense in memory. A loop that calls a merge function on each iteration would work, for example.
– orlp
Mar 12 at 22:08