Algorithms for almost sorting
Call an array $C$-sorted if each element is at-most $C$ places away from its place had the array been sorted (this is the same as &quot;almost&quot;-sorted array in the question, but in plain English).
Assume we will use comparison sort.
Claim One: Given an array of $n$ elements that is $C$-sorted,  we can sort it with at most $n\lceil\log_2 (C+1)\rceil$ comparisons.
Proof: Here is how we can sort the given array.

Create a buffer that is an array of size $C+1$.

One by one move the first $\min(n, C+1)$ elements to the buffer, keeping the buffer sorted using binary search to find the right place for each new element.

One by one move the min element from the buffer array to the result array, and, if the given array is not empty yet, add the next element to the buffer, keeping the buffer sorted using binary search to find the right place for that next element.


For each element in the array, at most $\lceil\log_2 (C+1)\rceil$ comparisons is used to find its right place in the buffer. The number of total comparisons used is at most $n\lceil\log_2 (C+1)\rceil$.  $\quad\checkmark$

Claim Two: At least $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons are needed to $C$-sort an array of size $n$ in the worst case. 
Proof: Otherwise, suppose there is an algorithm that can $C$-sort any given array of size $n$ with less than $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons. Extending that algorithm with the algorithm shown in the proof of claim one, we obtain an algorithm that can sort any given array of size $n$ with less than $\log_2(n!)$ comparisons. That is well-known to be impossible. $\quad\checkmark$

Claim Three: There is no algorithm that can $C$-sort an array of size $n$ with $O(\frac{n\log_2 n}{C})$ comparisons.
Proof: We have, if $n\ge C^{1+\epsilon}$ for some fixed $\epsilon\gt0$,
$$\begin{aligned}\lim_{C\to\infty} \frac{\log_2 (n!) - n\lceil\log_2 (C+1)\rceil}{\frac{n\log_2 n}{C}} &amp;= \lim_{C\to\infty} C\left(\frac{\log_2 (n!)}{n\log_2 n}-\frac{\lceil\log_2 (C+1)\rceil}{\log_2 n}\right)\\&amp;\ge \lim_{C\to\infty} C\left(1-\frac1{1+\epsilon}\right)=\infty. 
\end{aligned}\quad\checkmark$$

Indeed, $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ given a pretty strong lower bound for the number of comparison needed in the worst case since
$\log_2 (n!)$ is the lower bound to ordinarily sort an array, and, as $\log_2(n!)\approx n\log n$, for any fixed $C$,
$$n\lceil\log_2 (C+1)\rceil = o(\log_2 (n!)).  \ \ \color{#d0d0d0}{\text{(small o, not big O!)}}$$
That is, at least $(1-\epsilon)\log_2(n!)$ comparison is needed to $C$-sort array when $n$ is sufficiently large, for all fixed $\epsilon\gt0$ and $C$.

We also note that

on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A comparison sort cannot use less than $\log_2(n!)$ comparisons on average to sort $n$ items (as explained in the article Comparison sort) and in case of large $n$, Stirling's approximation yields $log_2(n!) \approx n(\log_2 n − log_2 e)$, so quicksort is not much worse than an ideal comparison sort.


Now let us have an array of $n=1000$ elements and $C=10$.

Quicksort will perform about $2n\log n\approx 19931$ comparisons on average to sort the array, as shown on Wikipedia.
Claim Two says $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil\approx4529$ are needed to $10$-sort the array in the worse case, which is sort of information-theoretical the best.
Note that $\frac{n\log_2 n}{C}\approx997$, which is much less than
of 4529.

So I believe, (some more argument are omitted here), an algorithm that performs about $n\log_2(n/C)\approx6643$ comparisons to $10$-sort the array is pretty much about the best we can get.