How to find big-O for an in-place perfect shuffle algorithm

Question

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of the items that got moved, then repeating for the remaining 1/2 array.

Unscrambling the permutation uses the fact that left items move into the right side with an alternating "add to end, swap oldest" pattern. We can find the i'th index in this permutation with this this rule:

For even i, the end was at i/2.
For odd i, the oldest was added to the end at step (i-1)/2

This gives this O(1) amortized oracle function:

$$ next(i) := \begin{cases} i/2 & \text{if $i$ is even;}\\ next( (i-1)/2) & \text{otherwise.} \end{cases} $$

(This is A025480)

The other complication in unscrambling is that while putting items back into place, sometimes the source index has already been used as a destination. Traditionally, this is where you would use an algorithm to find cycle leaders, guaranteeing minimal data movement at the cost of additional space or time. This algorithm just advances through the permutation, swapping every item into place, and running the next_index calculation again whenever it encounters a source which has already been swapped elsewhere. See the 'while' loop below.

Given a sequence $A$ of length $n$, consider it as two parts: $L = A_0 \ldots A_{m-1}$ and $R = A_m \ldots A_{n-1}$ where $m$ is $\lfloor n/2 \rfloor$. Then interleave($A$) will produce $R_0, L_0, R_1, L_1, \ldots$

$$ interleave(A) := {\\ m \leftarrow \lfloor n/2 \rfloor \\ \text{let }L = A_0 \ldots A_{m-1} \\ \text{let }R = A_m \ldots A_n \\ \text{for } i \text{ in } 0 \ldots (m-1): { j \leftarrow next(i) \\ \operatorname{exchange} L_i, R_j }\\ \text{for } j\text{ in } 0 \ldots ( \lfloor m/2 \rfloor -2): {\\ k \leftarrow next(\lfloor m/2 \rfloor + j) \\ \text{while } k < j : k \leftarrow next(\lfloor m/2 \rfloor + k) \\ \operatorname{exchange} R_j, R_k} \\ \text{if } n - m > 1 : { \\ b \leftarrow 1 \text{ if $m$ is odd; } 0 \text{ otherwise} \\ \operatorname{interleave} R_b \ldots R_{n-m-1} } } $$

The number of swaps is strictly 1.5 N. The question I have is: What's the big O of the index calculation in the unscramble step?

I think, in the hypothetical worst case, where every item is one slot above its destination, you would do 1+2+3+...+N/4 calls to next_index in the first pass. That works out to N^2/32 which is still O(N^2).

But the placement pattern never gets close to that worst case. Half the items are guaranteed to only need one lookup: the last half of the permutation contains every other item in increasing order - these will be swapped directly into place. And the remaining number of lookups depends on the number of cycles in the permutation - which seems to follow A006694.

Empirically it seems to be significantly less than N lg N - Here's a graph of calls to next_index vs N, with N lg lg N overlaid.

I'd like to learn how to calculate the actual growth.

---

C implementation.

int next_index(int n) {
  while (n & 1) { n = n >> 1; }
  return n >> 1;
}

void interleave(value_t A[], int n) {
  int i, j, k;
  int m = n/2;
  value_t* L = A;
  value_t* R = A+m;

  // Place 1st half
  for (i=0; i < m; i++) {
    j = next_index(i);
    SWAP( L+i, R+j);
  }

  //unscramble step
  for (j=0; j < m/2 -1; j++) {
    k = next_index(m/2 + j);
    while (k < j) {
      k = next_index(m/2 + k);
    }
    SWAP( R+j, R+k);
  }
  if (n-m > 1) {
    int b = (m&1) ? 1 : 0;
    interleave(R+b, n-m-b);
  }
}