Sorting lower bounds for almost sorted array
Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $A_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$, this runs in time $O(n\log k)$.

To see that this works, note that the first element in the sorted array must be one of the first $k+1$ elements, and in particular it must be the minimum of these elements. The second element could be any of the remaining elements or the $(k+2)$'th element, and in particular it must be the minimum of these elements. And so on.

For the lower bound, partition $n$ into blocks of length $k$, and consider the set of all permutation which fix each block. The number of such permutations is
$$
k!^{n/k} = [\Omega(k)^k]^{n/k} = \Omega(k)^n.
$$
Hence the number of comparisons is at least $\log [\Omega(k)^n] = \Omega(n\log k)$.