Generate The SUDSI Sequence

Mathematica, 88 bytes

Last[f@n_:=n;(r=f@1;{f@a,f@b}={f[b=+##],f[a=Abs[#-#2]]};r)&@@f/@{#,#+1}&/@Range@Input[]]

This is a full program, reading the input from a prompt. It's a very direct implementation of the definition, where I'm keeping track of the current sequence in f (whose values f[n] default to n).

Here is a slightly more readable version:

Last[
  f@n_ := n;
  (
    r = f@1;
    {f@a,f@b} = {f[b=+##],f[a=Abs[#-#2]]};
    r
  ) & @@ f /@ {#,#+1} & /@ Range @ Input[]
]

Some analysis

I've plotted the first 2000 elements of the sequence (it doesn't really get more interesting afterwards):

So the sequence is essentially linear with slope 2 and always has a few of those steps. It seems that the steps grow sublinearly (if they aren't even bounded), since they become barely noticeable as you increase the number of points you plot.

We can justify the linear growth quite easily (this is a bit handwavy, but I think it would hold up to a rigorous proof by induction): initially, the maximum affected number of a permutation step at n is n + (n+1) = 2n + 1. Also note that these numbers will always be moved to 1, since |n - (n+1)| = 1. So it's not surprising that we get numbers which are approximately 2n in the sequence. However, we can also note that for steps up to n, S_n+1 is always bounded by n+1, which means that no swapping step can swap two numbers which are both greater than n. Hence, numbers that still need to be processed will be less than or equal to their initial value. Hence, 2n + 1 is also the bound for the sequence itself.

I think finding an argument for the length of the steps will be trickier.

Pyth, 45 41 40 38 bytes

MXGH_HhugGm@Gtd,s<>GH2.a-@GH@GhHtQr1yQ

I noticed (as did Martin Büttner), that the maximum affected number of a permutation step at k is 2k + 1. But since we only have n - 1, steps, we only need a list of the numbers up to 2n - 1.

Try it online: Demonstration

M                       define a function g(G, H): return
                        (G is the list of numbers, H is a tuple)
 XGH_H                     a translation of G
                           (replaces the elements in H with the elements in reversed H)
                           in this application it swaps two values in the list G


                        implicit: Q = input()
 u     tQr1yQ           reduce, G = [1, 2, ..., 2*Q-1]
                        for each H in [0, 1, ..., Q - 2]:
                           G = 
  gG...                        g(G, ...)
h                       print the first element of the resulting list

And the second argument ... of the function call g is:

     ,                  create the tuple (
      s<>GH2               sum(G[H:][:2]), 
            .a-@GH@GhH     abs(G[H],G[H+1])
                        )
m@Gtd                   and map each value d to G[d - 1]

CJam, 45 40 39 bytes

Just a naive approach. Can be golfed further. Missing a array swap function too much.

ri_K*,\{\:L>2<L1$:+:S@:-z:DL=tDSL=t}/1=

How it works:

ri_                             "Read the input, convert to integer and copy it";
   K*,                          "Multiply the copy by 20 and get 0 to 20*input-1 array";
      \{ ... }/1=               "Swap and put input on stack and run the loop that many";
                                "times. After the loop, take the second element as";
                                "we have a 0 based array while series is 1 based";
{\:L>2<L1$:+:S@:-z:DL=tDSL=t}
 \:L                            "Swap to put iteration index behind the array";
                                "and store array in L";
    >2<                         "In each loop, the iteration index will be on stack";
                                "Get the two elements from the array starting at that";
       L1$                      "Put the array on stack and copy the tuple";
          :+:S                  "Get the sum and store it in S";
              @:-z:D            "Get the absolute difference of the tuple and store in D";
                    L=t         "Put the element at S diff at sum index";
                       DSL=t    "Put the element at S sum at diff index";

Try it online here