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.

  • $\begingroup$ It seems that A110316 is of interest here, which I found by counting the number of possible solutions per $n$. $\endgroup$
    – orlp
    Mar 12 at 21:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Mar 12 at 21:47
  • $\begingroup$ @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. $\endgroup$
    – orlp
    Mar 12 at 22:02
  • $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Mar 12 at 22:06
  • $\begingroup$ @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. $\endgroup$
    – orlp
    Mar 12 at 22:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.