Algorithms for sorting under some restrictions

Question

I was recently sorting a large list of names - I just ended up sorting it in Python, but it inspired in me the following question. If we're given a list $L$ of $n$ numbers, but can only see $k$ contiguous elements at a time and can shift a group of elements at once, what would be the fastest way to sort this list?

I originally had the list of names in Notepad. You can only see up to the number of rows at once, but you can cut and paste a bunch of rows at once. What I started to do is organize it into bunches of runs, but then you run into the problem of having two runs that are separated by a long gap (like as in the final step of merge sort, the two halves are separated by a large gap).

Let's say for concreteness that in this problem, there are three operations available to you given a view of the list $L[i+1]$ to $L[i+k]$: "cutting" from $m$ to $m+j$ with $i+1\le m$ and $m+j\le i+k$ (i.e. removing that range from the list, and storing that range in memory), changing the view to see some different group of $k$ (which takes time linearly proportional to the change in the view), and "pasting"/inserting all of memory to a location in the current view. Also, a cut operation can't be followed by another cut operation without first pasting it, and the only memory available is what you have in the "clipboard" (and maybe some constant size of memory not dependent on $k$ or $n$ - EDIT: this could be $O(\log n)$ additional memory instead, since otherwise, you couldn't store indices). Let's also say that comparisons take no time.

I don't think we can reach the $O(n\log n)$ efficiency of sorting algorithms like merge sort and quicksort in general, especially when $k$ is small in comparison to $n$ because you're limited in the amount you see at once. For example, if $k=1$, then I think the best you can do is something like insertion sort or selection sort for an $O(n^2)$ efficiency. But if $k>n$, then you can just do a normal merge sort or quicksort for $O(n\log n)$ efficiency.

What would the runtime be in the general case with an optimal algorithm (and what would the optimal algorithm be)? I'm mainly interested in asymptotic running time, rather than practical approaches, although those are of interest too.

Also, if there's anything vague in the question, or something that seems different to what I may have intended, please let me know.

Answer 1

With $k=1$ you can solve this in $O(n \log n)$ time using sorting networks.

Pick a sorting network of size $O(n \log n)$. You can implement each comparator using $O(1)$ steps, in your model. (To compare-and-sort the items at indices $i,j$, first cut the item at $i$ into memory, then move the window to $j$, then insert $i$ at the appropriate location before or after the item at $j$, then cut the other item and move it to $j$. This requires only $O(1)$ space, to store the indices $i,j$.) It follows that you can implement the sorting network in $O(n \log n)$ steps in your model, which in turn suffices to sort.

This is completely impractical, as the constant factors hidden in the big-O notation are enormous. A more practical algorithm would be to use bitonic mergesort or the pairwise sorting network, whose asymptotic time is $O(n \log^2 n)$, but whose constant factors are much more reasonable.

---

As Yves Daoust explains, "Your model does not account for the time to scroll the window. IMO this can be the dominant cost." This means that my answer is totally useless for the Notepad scrolling issue you actually ran into, because we must account for the time to scroll. That is treated above as taking $O(1)$ time regardless of how far you scroll, which is not realistic in practice.