I created the (balanced?) binary tree of all length $n$ permutations in a greedy manner: for each permutation and each pair of numbers I computed whether they appear in ascending order or not, and then I proceeded to greedily select the best pair of numbers to compare so as to produce as balanced a tree as possible; this means that different levels in different branches can look at different pairs of numbers.
Here is the tree I obtained for length $4$, with $<$ meaning the two numbers appear in ascending order, and $>$ that they appear in descending order.
I haven't proven it, but indeed it appears that the depth of this greedily-constructed balanced binary tree is bounded by $\lceil \log_2 n!\rceil$, and so each permutation can be represented by at most that many comparisons about pairs of elements appearing ascending or descending.
Question #1: For a particular permutation, how could I compute the shortest list of necessary comparisons that uniquely define that permutation? I can't use the same method as I've used to construct this tree, as to balance it I needed to generate all $n!$ permutations, computation which is not feasible for large $n$; and if I don't compute all permutations I can't balance the tree and a non-balanced tree does not obey the $\lceil \log_2 n!\rceil$ bound on depth.
Question #2: Given two different permutations, which correspond to two different nodes in this tree, how could I compute the number of comparisons they agree on (out of all possible $n(n-1)/2$ comparisons)?
Question #3: can you confirm / share a link to a proof that a greedily-balanced binary tree of permutations obeys the $\lceil \log_2 n!\rceil$ bound on depth?
Best Answer
Finding the shallowest comparison tree to sort $n$ objects is in general an open problem. According to the OEIS page for the optimal comparison numer, we only know these numbers up to $n=15$. Furthermore, the optimal number of comparisons to sort $12$ items is $30$, which is one more than $\lceil \log_2 12!\rceil=29$. This answers your question $3$ in the negative.
For question $1$, any permutation can be defined by $n-1$ comparisons, and no fewer. For example, when $n=5$, the permutation $[2,4,1,5,3]$ is uniquely specified by these four comparisons: $$ 2<4,\quad 4<1,\quad 1<5,\quad 5<3 $$ To see this is optimal, note that if only $n-2$ comparisons are given for the permutation $\pi=[\pi_1,\pi_2,\dots,\pi_n]$, then there must exist some $i\in \{1,\dots,n-1\}$ for which the comparison $\pi_i < \pi_{i+1}$ is not given. This implies the given comparisons cannot distinguish $\pi$ from the permutation resulting from switching $\pi_i$ and $\pi_{i+1}$ in $\pi$.
You can see the problem of finding the optimal set of comparisons to specify a permutation is trivial, and unrelated to the comparison tree.
Finally, for question $2$, given two permutations $\pi$ and $\tau$ of $\{1,\dots,n\}$ you want a way to compute the number of unordered pairs $\{i,j\}$ for which $\pi_i$ and $\pi_j$ appear in the same order in $\pi$ as $\tau_i$ and $\tau_j$ do in $\tau$. This is equal $\binom n2$ minus the number of inversions of $\pi\circ \tau^{-1}$. To compute this, you can
Compute $\tau^{-1}$. This takes $O(n\log n)$ time.
Compute $\pi\circ \tau^{-1}$. Should take $O(n)$, if you use arrays, I think?
Compute the number of inversions of $\pi\circ \tau^{-1}$. This takes $O(n\log n)$; see this Stack Overflow post for the method.