# Restore the original array after merge Sort based on it's steps

i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left subarray is chosen and 2 means element from right subarray is chosen. how can i do it? specially i have problem on that part that merge sort appends what ever is left from a subarray to final list. for example: it's given 12212 as input string on an array of numbers [1,2,3,4]. it means that there is a permutation of numbers 1 to 4 that if you give it to merge sort, it will give you 12212. that permutation is 2 4 3 1 .

For simplicity I will assume that the number $$n$$ of elements is a power of $$2$$. The same idea works in general (by suitably rounding the sub-array sizes according to the implementation of Mergesort at hand).

Let's pretend that, whenever two arrays of size $$x$$ are merged in the mergesort algorithm, they contribute exactly $$2x$$ digits to your input "merge string" $$m$$.

In the last call of the mergesort algorithm the final sorted array $$S$$ was constructed my merging two sub-arrays $$A$$ and $$B$$ with $$n/2$$ elements each. These sub-arrays $$A$$ and $$B$$ can be recovered by looking at the last $$n$$ digits of your input "merge string" $$m$$ and proceeding backwards.

In details, you can start with two empty arrays $$A$$, $$B$$ and a string $$m_S$$ containing the last n digits of $$m$$ and repeat the following step $$n$$ times:

• Let $$x$$ be the last digit of $$m_S$$.
• If $$s=1$$, add the last element $$S$$ to the beginning of $$A$$.
• Otherwise (if $$s=2$$), add the last element of $$S$$ to the beginning of $$B$$.
• Delete the last element of $$S$$ and the last digit of $$m_S$$.

Moreover, the remaining digits in $$m$$ (all but the last $$n$$ digits) can be (evenly) split into $$2$$ sub-strings $$m_A, m_B$$, where $$m_A$$ (resp. $$m_B$$) is the "merge string" resulting by using mergesort from sorting the first (resp. second) half of the elements into $$A$$ (resp. $$B$$).

Then you can apply the above strategy recursively on the sorted array $$A$$ with "merge string" $$m_A$$ and on the sorted array $$B$$ with "merge string" $$m_B$$. Eventually you'll reach a call in which the sorted array is just a single element, which must coincide with the input of the corresponding call of Mergesort.

A high level pseudocode could be the following:

// Returns the original order of the elements in S
Recover-Array(S, m):
if |S| == 1:
Return S

Decompose m into three parts m_A, m_B, m_S such that |m_A| = |m_B| and |m_S|=|S|
Split S into A, B according to the digits in m_S (as described above)

A' = Recover-Array(A, m_A)
B' = Recover-Array(B, m_B)

return the concatenation of A' and B'


Let's now consider the case in which the merge operation of mergesort stops contributing digits to the merge string as soon as all the elements from one of the two input arrays are merged (since the leftover elements in the other array can simply be appended to the output).

Once all complete merge strings for all the recursive calls of Mergesort are known then you can also recover the original array using an approach similar to the previous one.

In order to recover the complete merge strings imagine visiting the recursion tree of mergesort in postorder (i.e., you start with the leftmost leaf, then visit its sibling, then their parent, etc). This is exactly the order in which merges are performed. Whenever you visit a generic internal node $$u$$ whose subtree has height $$h$$, the corresponding merge procedure of Mergesort merged two arrays $$A$$ and $$B$$ of size $$2^{h-1}$$ into an array $$S$$ of size $$2^{h}$$ and appended a contiguous sequence of bits, which we will call a trace, to the our input merge string. (Leafs have empty traces). The idea is that, when $$u$$ is visited, we will have already recovered the complete merge strings for all its proper descendants and we will also have removed the bits corresponding to their traces from the input merge string. In this way the current fist digit of the merge string corresponds to the first decision taken by the merge procedure for $$u$$'s call.

To recover the complete merge string $$m_u$$ for an internal node $$u$$ find the shortest prefix $$m_S$$ of the current merge string that has either $$2^{h-1}$$ ones, or $$2^{h-1}$$ twos. This corresponds to the comparisons performed to merge all elements from one of $$A$$ and $$B$$ into $$S$$, i.e., $$m'_u$$ is exactly the trace for $$u$$'s call. To complete it into $$m_u$$, it suffices to add the missing $$2^h - |m'_u|$$ digits as a suffix (which corresponds to copying the leftover array). Then, we delete the trace $$m'_u$$ of $$u$$ from the input merge string and continue with the postorder visit.

• i think your algorithm doesn't cover situations where one of subarrays left or right just got appended to list. So to split m to ma and mb, one of them can be much less and ma! =mb. If it does, can you elaborate more? How does full psudocode look like?
– vhd
Dec 24, 2023 at 3:22
• Your strategy for recovering the complete $m_s$ does not look right to me. The substring ${m'}_s$ determined as you describe does not necessarily correspond to the start of a merge. To complete it, it might be necessary both to append absent digits and to include additional preceding digits. For example, in a 2+2 merge, you might have a trace 1, 2, 2, <omitted 1>, but your approach will mistake that for (1 from a previous trace), 2, 2, <omitted 1>, <omitted 1>. Dec 24, 2023 at 3:41
• @JohnBollinger you are right. Thank you! I edited my answer to reconstruct the complete traces from the beginning of the string, which avoids this ambiguity. Dec 24, 2023 at 9:19