关于Ford-Johnson算法中Beta插入顺序的澄清与技术问询

我的现有理解（若有误请指正） #

• Ford-Johnson算法一般以递归方式实现，每个递归层级接收一个数字序列
• 将序列中的元素两两配对，通常是相邻元素配对
• 每对中的较大值（称为alpha）放入新列表，传入下一层递归；较小值（称为beta）放入单独的待插入列表，留到后续步骤插入
• 递归触达基准案例后开始回溯，逐步将各层级的beta元素插入到mainChain中，最终得到排序完成的列表
• 在每个回溯层级，利用Jacobsthal序列确定beta插入mainChain的顺序

核心问题 #

当生成用于插入的Jacobsthal索引（例如待插入列表对应的[0,1,3,2,…]）时，这些索引是基于：

1. 首次配对时的原始未排序顺序（即待插入列表中存储的是第一对的B0、第二对的B1……），还是
2. 配对alpha在已排序mainChain中的位置（即B0是与mainChain最前端alpha配对的beta，B1是与下一个alpha配对的beta，本质上先按alpha位置重排待插入列表再应用Jacobsthal序列）？

我的困惑 #

如果alpha在mainChain中发生重排（比如alpha 5左移），为什么使用原始索引仍能最小化比较次数？

• 若alpha在递归过程中打乱了顺序，基于原始索引的Jacobsthal序列如何保证最优的搜索范围？

内容的提问来源于stack exchange，提问作者hermeszi