<p>If (1) the two interleaved sequences can form one monotonic sequence when un-interleaved, <em>and</em> either (a) the array starts with the lowest number and is of odd length, or (b) the array starts with the lowest number of the second sequence (the one that will be the right side when un-interleaved) and is of even length, we may be able to reverse the algorithm decribed in <a href="https://arxiv.org/abs/0805.1598" rel="nofollow noreferrer"><em>A Simple In-Place Algorithm for In-Shuffle</em> (Peiyush Jain, 2008)</a>.</p>

<p>We would have to perform the "cycle leader" sequences first, followed by the cycle shifts.</p>

<p>Example 1</p>

<pre><code>[1, 7, 2, 8, 3, 9, 4, 10, 5]
 1  2  3  4  5  6  7   8  9
 1  6  2  7  3  8  4   9  5

|1| unaffected

   |1     3                |
   m = 4; 2m = 3^2 - 1
   cycles start on 3^0, 3^1
   (4 swaps with 7 and the other
    numbers form a longer cycle.)
</code></pre>

<p>Example 2 (simple):</p>

<pre><code>[1, 5, 2, 7, 3]
 1  2  3  4  5
 1  4  2  5  3

|1| unaffected

   |          |
   m = 1
   cycle in 2m =&gt; 2, 5
   cycle in 2m =&gt; 3, 7
   cycle shift by m between 5 and 3
   =&gt; 2, 3, 5, 7
</code></pre>

<p>I wouldn't expect anyone to come up with this in an interview without being allowed to research, though :)</p>
Sorting an array with two sorted sequences in alternate position in linear time and constant space
<p>This was asked to me today in an interview and was kicked out after staring at the question for 5 min.</p>

<blockquote>
  <p>Given an array <em>A</em> such that the subsequence of all the odd positions ([<em>A</em><sub>1</sub>, <em>A</em><sub>3</sub>, <em>A</em><sub>5</sub>,&nbsp;&hellip;]) and the subsequence of all the even positions ([<em>A</em><sub>2</sub>, <em>A</em><sub>4</sub>, <em>A</em><sub>6</sub>,&nbsp;&hellip;]) are each in sorted order &mdash; e.g. [1, 7, 2, 8, 3, 9, 4, 10, 5] or [3, 8, 4, 11, 5] or [5, 2, 7, 4] &mdash; sort <em>A</em> in O(<em>n</em>) time and O(1) space (including stack space and output array space).</p>
</blockquote>

<p>I have racked my brain and picked my friend's over it for the last two hours. Google did not yield any answers. I do not want to color any opinions but I feel like this might not be possible to solve in the given complexities.</p>

<p>How can we solve this? All inputs are appreciated.</p>