(a) If $t_{k}$ is the number of times that volume $k$ is selected, then we have $t_{k} \leq 1 + (t_{1} + t_{2} + \cdots + t_{k-1})$. This is because volume $k$ must move to the right between selections, which means some volume was placed to its left. The only way that can happen is if a lower-numbered volume was selected. This leads to the bound $t_{k} \leq 2^{k-1}$. Furthermore, $t_{n} = 0$ since the $n$-th volume will never be too far to the right. Therefore, if $N$ is the total number of moves, then

$$N = t_{1} + t_{2} + \cdots + t_{n-1} \leq 1 + 2 + \cdots + 2^{n-2} = 2^{n-1} - 1$$

and in particular the process terminates.

(b) Conversely, $2^{n-1} - 1$ moves are required for the configuration $(n, 1, 2, 3, \ldots, n-1)$ if the librarian picks the rightmost eligible volume each time.

This can be proved by induction: if at a certain stage we are at $(x, n-k, n-k+1, \ldots, n-1)$, then after $2^{k} - 1$ moves, we will have moved to $(n-k, n-k+1, \ldots, n-1, x)$ without touching any of the volumes further to the left. Indeed, after $2^{k-1} - 1$ moves, we get to $(x, n-k+1, n-k+2, \ldots, n-1, n-k)$, which becomes $(n-k, x, n-k+1, n-k+2, \ldots, n-1)$ after 1 more move, and then $(n-k, n-k+1, \ldots, n-1, x)$ after another $2^{k-1} - 1$ moves. The result follows by taking $k = n-1$.

### Part (a)
1. Initial Setup and Goal: We need to show that if the librarian repeatedly selects a volume that is too far to the right and inserts it in its correct position, then all volumes will eventually be in the correct order.

2. Invariant: Consider the invariant that after each move, the number of volumes in their correct positions either increases or stays the same. This is because each move places one volume in its correct position without disturbing the order of the volumes already correctly placed.

3. Termination: Since there are a finite number of volumes, and each move either increases the number of correctly placed volumes or leaves it unchanged, the process must eventually terminate with all volumes in their correct positions.

4. Conclusion: Therefore, the process will eventually result in all volumes being in the correct order.

### Part (b)
1. Claim: Each volume $k$ can be moved at most $2^{k-1}$ times. We will prove this by strong induction.

2. Base Case: For $k = 1$, as soon as volume 1 is moved to the leftmost position, it cannot be moved out again. Thus, volume 1 is moved at most once, which is $2^{1-1} = 1$ time.

3. Inductive Step: Assume that for all $j < k$, volume $j$ can be moved at most $2^{j-1}$ times. We need to show that volume $k$ can be moved at most $2^{k-1}$ times.

- Initially, volume $k$ can be moved to its correct position once.
- Any subsequent move of volume $k$ requires displacing it by moving a smaller number.
- By the inductive hypothesis, each smaller number $j$ can be moved at most $2^{j-1}$ times.
- The total number of moves for all smaller numbers is $1 + 2 + \cdots + 2^{k-2} = 2^{k-1} - 1$.
- Therefore, volume $k$ can be moved at most $1 + (2^{k-1} - 1) = 2^{k-1}$ times.

4. Upper Bound: For $n$ volumes, the largest number of steps is given by the sum of the maximum moves for each volume from 1 to $n-1$:
$$\sum_{k=1}^{n-1} 2^{k-1} = 2^0 + 2^1 + 2^2 + \cdots + 2^{n-2} = 2^{n-1} - 1$$

5. Sequence to Achieve Upper Bound: We claim that the sequence $n, 1, 2, 3, \ldots, n-2, n-1$ will achieve this upper bound. We prove this by induction on $n$.

- Base Case: For $n \leq 2$, the sequence is trivially sorted in $2^{n-1} - 1$ moves.
- Inductive Step: Assume the sequence $n-1, 1, 2, \ldots, n-2$ can be sorted in $2^{n-2} - 1$ moves.
- If we restrict ourselves from moving book 1 (thus book $n$ never moves), the last $n-1$ volumes follow the same rules as the sequence $n-1, 1, 2, \ldots, n-2$.
- By the inductive hypothesis, this takes $2^{n-2} - 1$ moves.
- Moving book 1 to the correct position results in $1, n, 2, 3, \ldots, n-2, n-1$.
- Applying the inductive hypothesis again to the last $n-1$ volumes takes another $2^{n-2} - 1$ moves.

6. Conclusion: The total number of moves is $2 \times (2^{n-2} - 1) + 1 = 2^{n-1} - 1$, completing the induction.

The final answer is $\boxed{ 2^{n-1} - 1 }$