在线性时间和恒定空间中以交替位置对两个排序序列进行排序

Question

今天在接受采访时向我询问，并在盯着问题5分钟后被踢出。

给定一个数组A，使得所有奇数位置（[A1，A3，A5，...]）的子序列和所有偶数位置（[A2，A4，A6，...]）的子序列各自按排序顺序 - 例如[1,7,2,8,3,9,10,10]或[3,8,4,11,5]或[5,2,7,4] - 在O（n）时间内排序A和O（1）空间（包括堆栈空间和输出数组空间）。

在过去的两个小时里，我绞尽脑汁，挑选了我的朋友。谷歌没有得出任何答案。我不想为任何意见着色，但我觉得这可能无法在给定的复杂性中解决。

我们怎么解决这个问题？所有输入都表示赞赏。

Answer 1

如果（1）两个交错序列在未交错时可以形成一个单调序列，并且（a）数组以最小数字开始并且具有奇数长度，或者（b）数组以第二个的最小数字开始序列（非交错时将是右侧的序列）并且长度均匀，我们可能能够逆转A Simple In-Place Algorithm for In-Shuffle (Peiyush Jain, 2008)中描述的算法。

我们必须首先执行“循环引导”序列，然后是循环移位。

例1

[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.)

例2（简单）：

[1, 5, 2, 7, 3]
 1  2  3  4  5
 1  4  2  5  3

|1| unaffected

   |          |
   m = 1
   cycle in 2m => 2, 5
   cycle in 2m => 3, 7
   cycle shift by m between 5 and 3
   => 2, 3, 5, 7

我不希望任何人在面试中拿出这个而不被允许研究，但:)