A bookshelf contains $n$ volumes, labelled $1$ to $n$, in some order. The librarian wishes to put them in the correct order as follows. The librarian selects a volume that is too far to the right, say the volume with label $k$, takes it out, and inserts it in the $k$-th position. For example, if the bookshelf contains the volumes $1,3,2,4$ in that order, the librarian could take out volume $2$ and place it in the second position. The books will then be in the correct order $1,2,3,4$.

(a) Show that if this process is repeated, then, however the librarian makes the selections, all the volumes will eventually be in the correct order.
(b) What is the largest number of steps that this process can take?
### 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 } \)