I hope this is helpful. Joriki's brute force calculations of minimal $m$ for small $n$ are quite interesting and indeed come close to your estimate of $\log_2(n!)$. If you're willing to sacrifice such efficiency in exchange for a simpler, algorithmic design, here's an alternative approach, following a well-trodden path. The number of bits is $m = \binom{n}{2} = \frac12 n(n-1)$.
Coxeter presentation of $S_n$
There's a well-known presentation of the symmetric group $S_n$ on $n$ symbols given by the $n-1$ Coxeter generators $\sigma_1, \dots, \sigma_{n-1}$, where $\sigma_i = (i\;\;i+1)$. Besides being involutions ($\sigma_i^2 = 1$), distant (non-consecutive) generators commute ($\sigma_i\sigma_j = \sigma_j\sigma_i$ for $|i - j| > 1$) and consecutive generators ($|i - j| = 1$) satisfy the braid relation
$$
\sigma_i\sigma_j\sigma_i = \sigma_j\sigma_i\sigma_j.
$$
Example for $n = 3$
The two generators are $\sigma_1 = (1\;2)$ and $\sigma_2 = (2\;3)$, and the $3! = 6$ elements of $S_3$ can be presented as words formed of these "swaps":
$$
\begin{array}{ccc}
\text{one-line} & \text{cycle} & \text{word} \\
\hline
123 & - & \\
213 & (1\;2) & \sigma_1 \\
132 & (2\;3) & \sigma_2 \\
231 & (1\;2)(2\;3) & \sigma_1\sigma_2 \\
312 & (2\;3)(1\;2) & \sigma_2\sigma_1 \\
321 & (1\;2)(2\;3)(1\;2) & \sigma_1\sigma_2\sigma_1 \\
\end{array}
$$
The lengths of these words are minimal, and I sorted them by len-lex order. Notice, there's just one permutation of length $3$, called the longest element, and it determines the length of the sequence needed for your encoding:
$$
m = \binom{n}{2} = \frac{n(n-1)}{2}
$$
since each symbol, thinking in the one-line notation, has to swap with each other symbol to form the permutation to completely reverses the sequence $(123 \mapsto 321)$.
So you could define your sequence of transpositions by this longest word: $\sigma_1^{s_3} \sigma_2^{s_2} \sigma_1^{s_1}$, where each $s_i \in \{0, 1\}$ and the composition of permutations is read from right to left as usual. But I think it's more natural to record the encoding as a string, read from left to right. (These conventions are arbitrary, and reversing just swaps out each permutation for its inverse):
$$
\begin{array}{cccc}
1\text{-line} & \text{word} & \text{verbose} & \text{encoding} \\
\hline
123 & - & \sigma_1^0\sigma_2^0\sigma_1^0 & 000 \\
213 & \sigma_1 & \sigma_1^1\sigma_2^0\sigma_1^0 & 001 \\
132 & \sigma_2 & \sigma_1^0\sigma_2^1\sigma_1^0 & 010 \\
231 & \sigma_1\sigma_2 & \sigma_1^1\sigma_2^1\sigma_1^0 & 011 \\
312 & \sigma_2\sigma_1 & \sigma_1^0\sigma_2^1\sigma_1^1 & 110 \\
321 & \sigma_1\sigma_2\sigma_1 & \sigma_1^1\sigma_2^1\sigma_1^1 & 111 \\
\end{array}
$$
Why does this work?
Beginning with a permutation in one-line notation, use a bubble sort algorithm to return the sequence to ascending order. Begin with the largest symbol $n$, and record the transpositions required to send it "home" (position $n$), then move on to the next largest symbol $n-1$, again recording transpositions needed to send it to position $n-1$. Continue all the way down. If we're recording these as a sequence of permutations in the usual function notation, then we record this sequence from right-to-left.
Here's an example of this process with the longest element $4321$ in $S_4$:
$$
\color{blue}{43}21 \overset{\sigma_1}{\mapsto}
3\color{blue}{42}1 \overset{\sigma_2}{\mapsto}
32\color{blue}{41} \overset{\sigma_3}{\mapsto}
\color{blue}{32}14 \overset{\sigma_1}{\mapsto}
2\color{blue}{31}4 \overset{\sigma_2}{\mapsto}
\color{blue}{21}34 \overset{\sigma_1}{\mapsto}
1234
$$
From right to left, this is the word
$\sigma_1\sigma_2\sigma_1\sigma_3\sigma_2\sigma_1$
which is of length $\binom{4}{2} = 6$, as expected.
What about for all the other permutations? At each stage, we're swapping a pair of symbols from decreasing to increasing order, recording a $1$ as it moves to the right. If a pair of symbols are already in increasing order, then we simply omit that swap, and record a $0$. As a consequence, for any permutation, the sequence of swaps will always be a subsequence of the longest word. For $n = 4$, this will be encoded as $s_1s_2s_3s_4s_5s_6$, where the permutation is presented as
$$
\sigma_1^{s_6} \sigma_2^{s_5} \sigma_1^{s_4} \sigma_3^{s_3} \sigma_2^{s_2} \sigma_1^{s_1}.
$$
The general patter should be clear.
Encoding for $n = 4$
To illustrate that this is indeed algorithmic, here are the results generated by a dozen or so lines of Python code for $n = 4$. As before, I've sorted the permutations by their encodings, first by length (total number of instances of $1$) then lexicographically.
$$
\begin{array}{ccc}
\text{one-line} & \text{encoding} & \text{length} \\
\hline
1234 & 000000 & 0 \\
2134 & 000001 & 1 \\
1324 & 000010 & 1 \\
1243 & 001000 & 1 \\
2314 & 000011 & 2 \\
3124 & 000110 & 2 \\
2143 & 001001 & 2 \\
1342 & 001010 & 2 \\
1423 & 011000 & 2 \\
3214 & 000111 & 3 \\
2341 & 001011 & 3 \\
3142 & 001110 & 3 \\
2413 & 011001 & 3 \\
1432 & 011010 & 3 \\
4123 & 111000 & 3 \\
3241 & 001111 & 4 \\
2431 & 011011 & 4 \\
3412 & 011110 & 4 \\
4213 & 111001 & 4 \\
4132 & 111010 & 4 \\
3421 & 011111 & 5 \\
4231 & 111011 & 5 \\
4312 & 111110 & 5 \\
4321 & 111111 & 6 \\
\end{array}
$$