I've (possibly as a consequence of reading graff's post, but I'm not sure), come up with two patterns that I think will solve all cases, but I'm still having the devil's own trouble translating them into code!

Here are the two graphically, with some (possible, but incomplete) pointer math attempting to describe the swaps.

An bigger even/smaller odd case:

p2+p2len            -3-2-1
p2                  +0+1+2
p1+p1len-6-5-4-3-2-1
p1      +0+1+2+3+4+5
         0 1 2 3 4 5 6 7 8 
        [a b c d e f 1 2 3] temp
                    [1]>>>>>>[1]       temp   = *(p2+0)
              [d]>>>[d]               *(p2+0) = *(p1+3)
        [a]>>>[a]                     *(p1+3) = *(p1+0)
        [1]<<<<<<<<<<<<<<<<<<[1]      *(p1+0) =  temp
                      [2]>>>>[2]       temp   = *(p2+1)
                [e]>>>[e]             *(p2+1) = *(p1+4)
          [b]>>>[b]                   *(p1+4) = *(p1+1)
          [2]<<<<<<<<<<<<<<<<[2]      *(p1+1) =  temp
                        [3]>>[3]       temp   = *(p2+2)
                  [f]>>>[f]           *(p2+2) = *(p1+5)
            [c]>>>[c]                 *(p1+5) = *(p1+2)
            [3]<<<<<<<<<<<<<<[3]      *(p1+2) =  temp    
        [1 2 3 a b c d e f]
[download]

The above looks like 3 reps of a loop. (But is that because 6-3 = 3 or just because The smaller is 3; or ... ). And code?

A bigger odd/smaller even case:

p2+p2len                  -4-3-2-1
p2                        +0+1+2+3
p1+p1len-9-8-7-6-5-4-3-2-1
p1      +0+1+2+3+4+5+6+7+8
         0 1 2 3 4 5 6 7 8 
        [a b c d e f g h i 1 2 3 4] temp  
                                [4]>>[4]      temp   = *(p2+3)
                        [i]>>>>>[i]          *(p2+3) = *(p1+8) 
                [e]>>>>>[e]                  *(p1+8) = *(p1+4)
        [a]>>>>>[a]                          *(p1+4) = *(p1+0)
        [1]<<<<<<<<<<<<<<<[1]                *(p1+0) = *(p2+0)
                  [f]>>>>>[f]                *(p2+0) = *(p1+5)
          [b]>>>>>[b]                        *(p1+5) = *(p1+1)
          [2]<<<<<<<<<<<<<<<[2]              *(p1+1) = *(p2+2)
                    [g]>>>>>[g]              *(p2+2) = *(p1+6)
            [c]>>>>>[c]                      *(p1+6) = *(p1+2)
            [3]<<<<<<<<<<<<<<<[3]            *(p1+2) = *(p2+2)
                      [h]>>>>>[h]            *(p2+2) = *(p1+7)
              [d]>>>>>[d]                    *(p1+7) = *(p1+3)
              [4]<<<<<<<<<<<<<<<<<<<<[4]     *(p1+3) =  temp
        [1 2 3 4 a b c d e f g h i]
[download]

The above looks like 4 iterations (because the smaller is length 4), but the first iteration requires 3 internal steps and the other 3 only 2? (How to code?)

I haven't convinced myself I don't need even/even and odd/odd cases yet.