Jelly, 22 bytes

ṪṭjI$ż“€€ß‘ȦƇ;ñ
ṙMç€MẎ

Try it online!

Outputs in the format [#disks, fromto] (e.g. [5, 12]). The two pegs we use are numbered 1 (starting peg) and 2.

I worked out the algorithm used here by myself, but I think it's a variation on @Neil's. The basic idea is to go through the disks in order from largest to smallest: the disk we're checking is moved from peg 1 to peg 2 (along with everything above it), then all remaining disks smaller than the one we're checking are moved from peg 1 to peg 2, then all disks are moved from peg 2 to peg 1. This ensures that the disk we're checking, and all larger disks, end up in order at the bottom of peg 1, thus once all the disks have been checked, all disks are in order on peg 1.

The I/O format in this question is somewhat verbose to comply with and makes up a significant proportion of the answer – 9 of the 22 bytes are spent meeting I/O format restrictions. (Because this problem can be solved using only two pegs, a more natural format would be along the lines of "number of disks to move from peg 1 to peg 2, then number of disks to move from peg 2 to peg 1", allowing zero-sized moves.)

Explanation

Main link

The main link takes one argument, the stack of disks on peg 1.

 ṙMç€MẎ
  M        For each maximal element in the list,
 ṙ           produce a list by rotating that element to the start;
    €        and for each {resulting rotated list}
   ç           call the helper link 1ŀ, with arguments {that rotated list}
     M         and a list of the locations of the maximal elements
      Ẏ      then concatenate the resulting outputs.

The main link determines a) what order the disks on peg 1 will be in after a series of three moves, and b) when to stop recursing. (Stopping the recursion is done by iterating over a list of lists produced from all maximal elements of the original list; there will be either 0 or 1 such element, thus either we do a 1-iteration loop in order to recurse, or a 0-iteration loop in order to stop recursing.)

Helper link 1ŀ

The helper link takes two arguments: the order the disks on peg 1 will be in after a sequence of three moves, and the number of disks that were moved by the first of those moves. (The second argument is taken as a 1-element list, because that's the format that the main link provides it in.)

The helper link is given only the relevant subset of the disks on peg 1 (i.e. not including disks that were already moved into place earlier). This means that the last element of the first argument is the disk that is being moved into place.

 ṪṭjI$ż“€€ß‘ȦƇ;ñ
  ṭ               Concatenate {the second argument}
 Ṫ                  and the last element of {the first argument};
   j              between those two elements, place
    I               the forward differences of
     $                the concatenated list (i.e. arg2 - last of arg1);
      ż           zip with
       “€€ß‘        [12, 12, 21];
             Ƈ    {in the resulting list,} keep only elements that
            Ȧ       contain no zeroes (including recursively)
              ;   and to {the result of that}, append
               ñ    {the result of} a call to the main link (see below)
 Ṫ                    in which the last element of {arg1} is deleted

The helper link basically just calculates the sizes of the moves (first the substack consisting of the disk that's being moved into place and the disks above it, then the rest of the portion of the stack we're looking at, and then the whole thing moved back the other way). The calculations are very easy but done in a bit of a weird order to reduce the need to spend bytes on plumbing (first we take the number of disks in the first move and the total nubmer of disks, then place the difference in between). The three moves are always in the same directions (1 to 2, 1 to 2, and 2 to 1), so that can be hardcoded; but we have to remove zero-sized moves (however, there's no requirement to remove redundant moves, so if the last disk we're looking at is already in place, the stack above it gets moved from 1 to 2 then 2 to 1 for consistency).

After the last disk is moved into place, the helper link recursively calls the main link to move all the previous disks, using ñ. As far as I can tell, this is somehow exploiting a bug in Jelly, because ñ is being used in a way that doesn't match its documentation – it is supposed to reparse the link being called as though it takes two arguments, but the main link doesn't parse correctly if you actually give it two arguments. Although I'm not sure, I think that what's happening is that the previous 1-argument call to the main link somehow ended up getting cached in a way that isn't invalidated properly. The correct way to call the main link would be to use Ñ, which specifies the correct (1-argument) parser to use; however, that would give it the wrong implicit argument, so I'd have to waste a byte to disambiguate as Ñ{ (specifying to use the left argument of the current link). In this case, ñ provides the main link with two arguments (the left and right arguments of the current link), but it's only a 1-argument link; fortunately, it happens to read from the correct argument, so everything works. In any case, the code appears to work, even though I don't fully understand why.

JavaScript (Node.js), 74 bytes

f=a=>(n=a.length)^(p=a.pop())?`a${n}b b${n-1}a b1a `+f([p,...a]):a+a&&f(a)

Try it online!

-1B Shaggy

while (remain) {
    while (bottom != length) {
        move bottom to top
    }
    ignore bottom
}

Ruby, 74... 65 bytes

f=->*l,m{l[-m]?"a#{k=l.max}b b#{k-1}a b1a "+f[m,*l]:m<2?"":f[*l]}

Try it online!

What

If the bottom disc is not the largest, move the whole stack to b, then all except one back, and the remaining one on top. This will "rotate" the stack, iterate until the largest disc is on the bottom.

If the largest disc is on the bottom, leave it alone and repeat the procedure for the remaining ones.

How

f=->*l,m{                       # m is the bottom of the stack
  l[-m]?                        # if l has at least m elements 
                                # (m is not the largest disc)
  "a#{k=l.max}b b#{k-1}a b1a "  # Move all, then put them back with the bottom disc on top
  +f[m,*l]                      # rotate the input list and repeat
  :m<2?""                       # m is the largest disc, if this is the last one stop
  :f[*l]}                       # otherwise repeat for the rest of the stack

Japt -x, 38 bytes

Yeesh! This is pretty hideous. And, in golfing it down, it evolved into an almost port of Mukundan's JS solution.

¬©" ab{T=Ub°V)Ä+TÎç" ba"+TUjT)+ß} ba1

Try it

¬©" ab{T=Ub°V)Ä+TÎç" ba"+TUjT)+ß} ba1     :Implicit input of array U
¬                                         :Join
 ©                                        :Logical AND with
  " ab                                    :  Begin string literal
      {                                   :  Interpolate
       T=                                 :    Assign to variable T
         Ub                               :      First 0-based index in U of
           °                              :        Prefix increment
            V                             :        Second input variable (which defaults to 0)
             )                            :    End assignment
              Ä                           :    Add 1
               +                          :    Concatenate
                TÎ                        :      Sign of T
                  ç" ba"+T                :      Repeat " ba"+T that many times
                          UjT             :      Remove & return the Tth element from U, mutating it (this gets passed as a second argument to ç, which only expects 1 argument)
                             )            :      End repeat
                              +ß          :    Concatenate a recursive call with implicit arguments U & V
                                }         :  End interpolation
                                  ba1     :  End string literal
                                          :Implicitly trim and output

Python, ⁸⁹ 86 bytes

f=lambda a:a and[f"a{(i:=a.index(min(a)))+1}b"]+(i>0*a.pop(i))*[f"b{i}a"]+f(a)+["b1a"]

Attempt This Online!

Uses an algorithm similar to the one @Arnauld uses, but instead constructs the reverse sorted order on the second peg and then moves elements one at a time from the second peg back to the first peg. Since the sequence was reversed on the second peg, moving elements one at a time back to the first peg will result in the sorted sequence.

JavaScript (Node.js), ⁸⁹ 88 bytes

-2 byte thanks to @Arnauld

f=(a,n=1)=>a+a&&`a${(i=a.indexOf(n))+1}b ${i?`b${i}a `:""}${f(a,n+1,a.splice(i,1))}b1a `

Try it online!

JavaScript (ES6), 97 bytes

A silly algorithm using only two pegs. The I/O format is the one used in the challenge.

f=(a,n=N=a.length)=>n?`a${(i=a.indexOf(n))+1}b ${i?`b${i}a `:""}`+f(a,n-1,a.splice(i,1)):`b${N}a`

Try it online!

Or 88 bytes with an alternate output format (N> to move N discs from a to b, N< to move N discs from b to a).

Algorithm

1. Take all discs in A up to the disc with the highest label included and move them to B.

   

2. Take all discs in B up to the disc with the highest label excluded and move them back to A. Or ignore this step if there's nothing to move.

   

Repeat steps 1 and 2 \$N\$ times even if the discs are already sorted. We end up with a sorted pile on B. Finally, move everything from B to A.

Charcoal, 48 45 bytes

Ｗ⌈Φθ›κ⊕λ«≔⊕⌕θιηＵＭθ⎇‹λι§θ﹪⁺ληικ⟦⁺abι⁺baη⁺ba⁻ιη

Try it online! Link is to verbose version of code. Outputs in the format [src][dest][#discs]. Explanation:

Ｗ⌈Φθ›κ⊕λ«

While at least one disc is out of place, get the highest valued such disc. Call this i.

≔⊕⌕θιη

Get is current index (1-indexed). Call this h.

ＵＭθ⎇‹λι§θ﹪⁺ληικ

Rearrange the discs in memory according to the following three movements, ready for the next iteration of the loop.

⟦⁺abι⁺baη⁺ba⁻ιη

Move i discs from a to b, then h discs from b to a, then the remaining discs from b to a.

Jelly, 23 bytes

NỤ>";\§ạƲż’$ṭLFJḂƝżƊṛ/Ƈ

A monadic Link that accepts the disks as an unordered list of a prefix of the natural numbers and yields a list of instructions. Each instruction is:

[[ToPeg, FromPeg], DiskCount]

where the initially full peg is 0 while 1 and 2 are the others (although we only use 0 and 1 anyway :p)

Try it online!

How?

The resulting algorithm

Pick up all the disks from the "Source Peg" and put them on another peg, the "Buffer Peg", then repeatedly (a) pick up as many disks as needed from the Buffer Peg to reach the largest disk and place them onto the Source Peg, and then, if possible, (b) pick up one less disk than in (a) from the Source Peg and place them on the Buffer Peg.

Code

NỤ>";\§ạƲż’$ṭLFJḂƝżƊṛ/Ƈ - Link: unordered list of [1..N], Disks
N                       - negate {Disks}
 Ụ                      - grade {that} up
                          -> Places = Disk indices sorted by Disk value, descending
        Ʋ               - last four links as a monad - f(Places):
    ;\                  -   prefixes of {Places}
   "                    -   zip with:
  >                     -     {Place} greater than {Prefix} (vectorises)
      §                 -   sums -> Counts
                              [count of values both earlier in Places and less than V
                               for V in Places] 
       ạ                -   {that} absolute difference {Places}
                            -> counts of disks to pick up from the Buffer Peg at
                               each iteration.
           $            - last two links as a monad - f(X=that):
          ’             -   decrement -> counts of disks to return to the Buffer Peg
         ż              -   {X} zip with {that} -> PairsOfCounts
             L          - length {Disks} (the initial move count)
            ṭ           - {PairsOfCounts} tack {that}
              F         - flatten -> AllCounts (plus a trailing zero)
                   Ɗ    - last three links as a monad - f(AllCounts):
               J        -   indices {AllCounts} -> [1..AllCounts]

                 Ɲ      -   for neighbouring pairs:
                Ḃ       -     mod two
                            -> [[1,0],[0,1],[1,0],[0,1],...]
                  ż     -   {that} zip with {AllCounts}
                      Ƈ - keep those for which:
                     /  -   reduce by:
                    ṛ   -     get right argument
                          (i.e. remove instructions where zero disks would be moved)