2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Constant additional space sounds like a severe restriction: you can't even remember an index into the array. Would you be satisfied with a solution that uses $O(\lg n)$ additional bits of memory, so that you can store a constant number of indices/pointers into the array? (How do you even implement something like insertion sort or selection sort without being able to store indices to the array?) $\endgroup$
    – D.W.
    Apr 19, 2023 at 20:41
  • $\begingroup$ Do you care about practical solutions, or asymptotic worst-case running time (i.e., theoretical complexity)? $\endgroup$
    – D.W.
    Apr 19, 2023 at 20:43
  • $\begingroup$ @D.W. You're right, I'll make the edit for $O(\log n)$ bits of memory, instead of $O(1)$ - thanks for pointing that out. And mainly asymptotic running-time, although I am interested in the practical solutions too. $\endgroup$ Apr 19, 2023 at 21:52
  • 1
    $\begingroup$ Your model does not account for the time to scroll the window. IMO this can be the dominant cost. $\endgroup$
    – user16034
    Apr 20, 2023 at 6:37
  • $\begingroup$ @YvesDaoust Yes you're right, I've added that in. $\endgroup$ Apr 22, 2023 at 6:00

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ "can only see $k$ contiguous elements at a time" - I think that word "contiguous" might be important. $\endgroup$
    – Pseudonym
    Apr 19, 2023 at 23:45
  • $\begingroup$ @Pseudonym, I don't understand your concern. I did notice that word "contiguous", and my scheme takes that into account. (Incidentally, when $k=1$ it makes no difference.) It sounds like you think there is something wrong with my answer -- might you be able to elaborate on what problem you are seeing? $\endgroup$
    – D.W.
    Apr 20, 2023 at 0:56
  • $\begingroup$ Ah, wait, I think I misunderstood the constraint. This part threw me: "given a view of the list $L[i+1]$ to $L[i+k]$". If $k=1$, then the number of useful comparisons you can perform is exactly zero. But this is contradicted by the last part of the question. $\endgroup$
    – Pseudonym
    Apr 20, 2023 at 4:11
  • $\begingroup$ @Pseudonym, if I understand the problem statement correctly, you can perform a comparison between $L[i]$ and $L[j]$ by looking at $L[i]$ to $L[i]$, copying it into memory, then looking at $L[j]$ to $L[j]$, comparing what is in memory to what you are looking at (the code is allowed to read both values), and then deciding whether to insert what's in memory just before $L[j]$ or just after based on the results of that comparison. $\endgroup$
    – D.W.
    Apr 20, 2023 at 7:55
  • $\begingroup$ @D.W. The way you read it is right - sorry for any ambiguity. Why wouldn't it be larger than $O(n\log n)$ (because of the window moves) though? $\endgroup$ Apr 20, 2023 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.