Note that each palindrome of length 9 can be written in the form $a$(palindrome of length $7$)$a$ where the first digit of the palindrome of length $7$ is allowed to be zero. Also, the palindromes of length $9$ in sorted order consist of $1$(palindrome of length $7$)$1$, ..., $2$(palindrome of length $7$)$2$, ... $9$(palindrome of length $7$)$9$. Also, note that $(a+1)$(smallest palindrome of length $7$)$(a + 1)$ $-$ $a$(palindrome of length $7$)$a$ is invariant for $1 \leq a \leq 9$. Thus, the answer consists of $(a+1)$(smallest palindrome of length $7$)$(a + 1)$ $-$ $a$(palindrome of length $7$)$a$ and $10$ times the answer for palindromes of $7$ where the first digit is allowed to equal zero (which can be found in a similar recursive fashion).