I’m working on the Ford-Johnson algorithm and trying to nail down the insertion order for betas.  I am unsure to apply the Jacobsthal numbers to the insertion indices tied to the original pairing order or mainChain alpha positions.

Here’s my understanding, please correct me if I’m off:

1. The FJ algo is usually implemented recursively, with each recursive level taking in a sequence of numbers.

2. We pair the numbers up, typically just with the number next to it in the sequence (adjacent pairing).

3. We then put the larger (alpha) of each pair into a new list, which gets passed to the next recursive level. The smaller (beta) from each pair is placed in a separate pending list for later insertion.

4. When the recursion reaches its base case and starts unwinding/returning, we progressively insert the betas from each level into a mainChain that will eventually become the final sorted list.

5. At each returning level, we insert the betas into the mainChain using the Jacobsthal sequence to determine the order.

My main question:
When we generate the Jacobsthal indices for insertion (e.g., something like [0, 1, 3, 2, ...] for a pending list), are these indices based on the original unsorted order from when we first formed the pairs (i.e., B0 from the first pair, B1 from the second pair, etc., as stored in the pending list)?
Or,
is the indexing based on the position of the paired alpha in the sorted mainChain (e.g., B0 would be the beta paired with the alpha closest to the front of the mainChain, B1 with the next, and so on, essentially reordering the pendings by alpha position before applying Jacobsthal)?

What I don't understand:
If alphas are reordered in mainChain (e.g., alpha 5 jumps left), why would original indices still minimize comparisons?

• If alphas shuffle during recursion, how does Jacobsthal (using original indices) guarantee optimal search ranges?