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.