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

Question

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 .

Answer 1

When you're recording the steps for a merge, you'll either get enough 1s to consume the whole left array OR enough 2s to consume the whole right array. For a 2+2 merge, these are the possibilities:

11
121
122
211
212
22

This set of strings is always prefix-free, meaning that if you know where the sequence for a merge starts, then you can tell where it ends.

Unfortunately, it's not suffix-free. It includes both 22 and 122, for example. That means that you can't tell where it starts by knowing where it ends. If your string ends in ...1122, for example, and you know that it ends in a 2+2 merge, it could be either a 22 merge or a 122 merge. There's no way to tell the difference without tracing all the merges from the start.

That makes it a little tricky to write your un-merge-sort function, because you have to start at the beginning of the step record string.

In fact, the easiest way to do this un-merge is:

1. Make a sorted array of the numbers from 0 to n-1
2. Mergesort the array, but use your index string instead of comparisons
3. Now you have an array that maps each position to the original index of the element that ended up there. Use this to undo your sort in O(n) time.