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)&amp;@@f/@{#,#+1}&amp;/@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
  ) &amp; @@ f /@ {#,#+1} &amp; /@ 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, Sn+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.