Javascript (ES6), 146 Bytes

s=>[...s].map(c=>c.charCodeAt(0)).sort((a,b)=>a-b).map(i=>i%s.length).reduceRight((c,a,i)=>{let t=c[i];c[i]=c[a];c[a]=t;return c},[...s]).join("")

Explanation

Uses the MATL answer's idea of just reversing the order of the swapping, but it utilizes array reduction.

Uiua, 18 bytes

∧⍜⊏⇌⇌≡⊟°⊏◿⊸⧻⍆⊸-@\0

Try it in the pad!

Exaplanation

Port of the MATL answer

∧⍜⊏⇌⇌≡⊟°⊏◿⊸⧻⍆⊸-@\0
             ⊸-@\0 # Covert to codepoints
            ⍆      # Sort
         ◿⊸⧻       # Modulus by length
     ≡⊟°⊏          # Zip with enumerate
    ⇌              # Reverse
∧⍜⊏⇌               # Swap each pair

Perl 5 -F, 64 bytes

$i=@F;@F[$i,$_]=@F[$_,--$i]for reverse map{(ord)%@F}sort@F;say@F

Try it online!

Vyxal, 12 bytes

Cs₅%ėṘ(ns⁽Ṙ¢

Try it Online!

Quite possibly the first time I've used ė (enumerate). Output as a char list.

 s           # Sort
C            # the input's charcodes
   %         # And modulo them by
  ₅          # the input's length
    ė        # enumerate, zipping with [0...len(input)] to result in a list of pairs of swaps
     Ṙ(      # and apply the swaps reversed:
           ¢ # In the current value, apply over the indices
       ns    # of the current swap, sorted (shouldn't be necessary, but there's a bug)
         ⁽Ṙ  # Reverse, swapping the two characters

K (ngn/k), 36 34 bytes

{x{x[y]:x@|y;x}/|+(!#x;(#x)!x@<x)}

Try it online!

As with the other answers, applies the swaps in the opposite order.

• (...;(#x)!x@<x) mod the sorted ASCII character codes by the length of the input
• (!#x;...) generate indices from 0..len(input)
• |+ transpose this pair of lists into a list of pairs, then reverse its order
• x{...}/ set up a fold, seeded with x (the original input), and this list of pairs indicating the order of the swaps
  • {x[y]:x@|y;x} swap the pair of elements of this current iteration, returning the modified list

Python 3, 143 bytes

def u(i):
 m=len(i);p=list;i=p(i);a=[x%m for x in sorted(p(map(ord,i)))]
 for l in range(1-m,1):i[-l],i[a[-l]]=i[a[-l]],i[-l]
 return''.join(i)

I found it easiest to transform the input to a list and then back again, but I wouldn't be surprised if there is a more compact way to accomplish this.

Try it online!

Scala, 101 92 bytes

s=>(s.sorted.map(_%s.size).zipWithIndex:\s){case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))}

Saved 9 bytes thanks to @user.

Straightforward monadic-style implementation:

• (s.sorted.map(_%s.size).zipWithIndex:\s) creates the array "A" and traverses its elements (incl. corresponding index) from right to left via folding (:\ = foldRight, accumulator initialized by input string s)
• {case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))} updates the accumulator value b by swapping b(i) and b(c). This part is quite verbose, since there is no b.swap(c,i) built-in.

Try it online!

Ruby, 70 bytes

->s{r=0;s.bytes.sort.reverse.map{|c|s[c],s[r]=s[r-=1],s[c%=s.size]};s}

Try it online!

05AB1E, 16 bytes

Ç{Dg%ā<øRvDyèyRǝ

Try it online or verify all test cases.

The shuffle method described in the challenge description would be this:

Ç{Dg%ā<øvDyèyRǝ

Try it online or verify all test cases.

And the top program simply reverses the list of indices to unshuffle.

We can add a trailing = after the programs above to see the intermediate steps: try it online.

Explanation:

Ç          # Convert the (implicit) input to a list of codepoint-integers
 {         # Sort them from lowest to highest
  Dg       # Duplicate, pop and push the length
    %      # Modulo the codepoints by this length
     ā     # Push a list in the range [1,length] (without popping)
      <    # Decrease each by 1 to make the range [0,length)
       ø   # Create pairs of the two lists
        R  # Reverse this list of pairs
v          # Loop over each pair of indices `y` of this list:
 D         #  Duplicate the current string
           #  (which is the implicit input in the first iteration)
  yè       #  Pop one string, and get the character-pair at indices `y`
    yRǝ    #  Insert them at back in the string at the reversed indices-pair `y`
           # (after the loop, the resulting string is output implicitly)

The swapping portion is taken from my answer here.

Brachylog, 82 bytes

lL∧L⟦₅R⁰∧?oạ%ᵐ↙L;R⁰z↔I∧?g,I↰ˡ↙1c
g;R⁰z{[[X,[A,B]],R]∧(A R∧X∋↙B.∨B R∧X∋↙A.∨X∋↙R.)}ᵐ

Try it online!

I couldn't find any reasonable way to swap 2 elements by index in Brachylog, so the second line is a verbose and ugly implementation of that.

Since Brachylog is prolog based, I could have applied the transform forwards and let it calculate the inverse automatically, but it was easier to just reverse the list.

Lua, 231 220 bytes

s=...t={}s:gsub(".",load('table.insert(t,(...):byte())u=s.sub'))table.sort(t)for i=#t,1,-1 do a=t[i]%#t+1 i,j=math.min(a,i),math.max(a,i)s=u(s,1,i-1)..u(s,j,j)..u(s,i+1,j-1)..(i~=j and u(s,i,i)..u(s,j+1)or"")end print(s)

Try it online!

R, 104 bytes

function(s){i=sort(v<-utf8ToInt(s))%%(n=nchar(s))+1
for(j in n:1)v[rev(w)]=v[w<-c(j,i[j])]
intToUtf8(v)}

Try it online!

MATL, 19 bytes

tStn\Q!tfhP!"t@)@P(

Try it online! Or verify all test cases.

Explanation

The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order.

t       % Input (implicit): string s of length N (row vector of chars of size 1×N)
S       % Sort (by ASCII codes)
tn      % Duplicate, number of elements: gives N
\       % Modulo (of ASCII codes), element-wise. Gives a 1×N numeric vector
Q       % Add 1 (because MATL uses 1-based indexing)
!       % Transpose into a column vector, of size N×1
tf      % Duplicate, find. Gives the N×1 column vector [1; 2; ...; N]
h       % Concatenate horizontally. Gives an N×2 matrix
P       % Flip vertically (for N=1 flips horizontally, but that still works)
!       % Transpose into a 2×N matrix 
!"      % For each column
  t     %   Duplicate the (partially processed) string: (*)
  @     %   Push current column: 2×1 vector of the form [s(k); k]: (**)
  )     %   Read elements (**) from string (*). Gives 2×1 char vector: (***)
  @P    %   Push current column, flip: gives [k; s(k)]: (****)
  (     %   Write (***) into (*) at positions (****)
        % End (implicit)
        % Display (implicit)

Python3, 155 bytes:

def g(s,x,l):
 for i in range(l):h=s[(j:=(l-1-i))];s[j]=s[x[j]];s[x[j]]=h;
def f(s):
 s=[*s];g(s,[ord(i)%(t:=len(s))for i in sorted(s)],t);return''.join(s)

Try it online!

J, ^{34 32} 31 bytes

<(C.>)/@,~i.@#;&~./@,.#|3 u:/:~

Try it online!

Uses Luis Mendo's insight "The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order."

After that, we turn the problem into a single fold of all the swaps, using J's "Permute" verb C., which can implement swaps directly. The only hiccup is that it doesn't allow self swaps, so we have to turn cases like 3 3 C. 'GOLF' into 3 C. 'GOLF', which we do by call unique &~. while creating the swap pair.

Charcoal, 47 bytes

≔⪪Ｓ¹θＷ⌊⁻θυＦ№θι⊞υιＷυ«≔℅⊟υι≔§θιη§≔θι§θＬυ§≔θＬυη»↑θ

Try it online! Link is to verbose version of code. Explanation:

≔⪪Ｓ¹θ

Split the input string into characters.

Ｗ⌊⁻θυＦ№θι⊞υι

Sort them in ascending order.

Ｗυ«

Process the sorted characters.

≔℅⊟υι

Get the ASCII code of the next character in reverse order.

≔§θιη§≔θι§θＬυ§≔θＬυη

Swap the character at the current index with the character at that position (cyclically reduced modulo the length of the string).

»↑θ

Output the final character array vertically so it prints as a string.

Vyxal, 30 bytes

:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹

Try it Online!

What a mess of 30 bytes. Probably gonna be outgolfed by better stack control.

Explained

:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹
:                              # Push two copies of the input string
 C                             # and get the character code of each letter in the second copy
  ₌sL                          # push that sorted and it's length (parallel apply)
     :‹£                       # place the length of the string - 1 into the register - this will keep track of the nth character we're getting
        %Ṙ                     # reverse the list of each character code modulo the length of the string - this gets us our modulo indices (A[n])
          (                    # for each index n in that list:
           :                   #   The top of the stack is the first copy of the input string from earlier - we want to preserve this because we're modifying it with assignment, so make another copy to extract characters from
            ¥n"İ               #  that string's (register)th and nth character
                n¥"            #  push the list [n, register]
                   $Z          #  and then push zipped([n, register], [(register)th char, nth char]) - this allows us to create a list of [index to assign, character to assign]
                     ÷→        #  Place the last pair into the ghost variable for a bit, as we need to focus on the first pair of assignment.
                       ÷Ȧ      #  string[n] = (register)th char
                         ←÷Ȧ   #  string[register] = nth char
                            &‹ #  Increment the register to swap the next character position.
                               # After all that, the final string is implicitly printed.