# What is the maximum total displacement needed for sorting a list? [duplicate]

I imagined a system of $n$ "things" that are ordered: each "thing" has a specific place. Also, the $n$th thing is the last thing in the system, meaning that there is always a "thing" to which number $1$ is assigned. Given such a system, we can "mess it up" — put things in wrong order. Now we must put them back. Like so (an example):

We see that in this case, we have a system $n = 5$. If all the "things" are in their spots, then the output of the function I wanted to deduce (but failed) is $0$. But if they are not, my "function" adds $1$ to its output for each place a misplaced "thing" must travel to get to its original location. In the above case, the output of function in order to "clean up the mess" is $8$.

The question is: for some system $n$ (where $n \in \mathbb{N}$), what is the maximum of the function $f$?

I already found $f_{\text{max}}$ for $n = 1$ ($f_{\text{max}}(1) = 0$), $n = 2$ ($f_{\text{max}}(2) = 2$) and $n = 3$ ($f_{\text{max}}(3) = 4$). But it is quite clear that this problem needs a different approach; bruteforce won't do any good. So, my main interest is to know what a formula for $f_{\text{max}}(n)$.

I am very eager to see the answer. I tackled a few hard problems, but this one (and the strange thing is that I made it up myself) is one tough cookie, at least for me.

## marked as duplicate by Rahul, Community♦Dec 2 '17 at 18:19

• I seem to have had my comment deleted? – Paul Aljabar Dec 2 '17 at 18:24
• @PaulAljabar What? I have no idea how this happened! – Gregor Perčič Dec 2 '17 at 18:44

It seems clear that the maximum occurs when you reverse the sequence. Consider the cases $n$ odd and $n$ even separately, and add up the number of positions each item has to move. For example for $n$ odd, the sum is $2(2+4+\,...+\,n-1)$ and for $n$ even it is $2(1+3+5+\,...\,+n-1)$. Work it out to show that for $n$ odd $$f_{odd}(n)={1\over2}(n^2-1)$$ and for $n$ even, $$f_{even}(n)={1\over2}n^2$$

• This is a duplicate of this question - see also the good blog post here – Paul Aljabar Dec 2 '17 at 20:21
• Actually, the two results are the same. In the answer you refer to, the notation is different (it is not expressed in terms of $n$). Do the substitution and you will find the results agree. (This comment was for a previous version of Paul's comment where he claimed this answer is incorrect). – Dean Dec 2 '17 at 20:22
• Yes, I got that. Just wanted to make it clear that it is a duplicate. – Paul Aljabar Dec 2 '17 at 20:24

I think (one) most messed up configuration is given by $n,n-1,n-2,\ldots, 1$. $1$ and $n$ have to travel $n-1$ positions, $2$ and $n-1$ have to travel $n-3$ positions and so on. So I think if $n$ is even you have maximal $2*((n-1)+(n-3)+\ldots +1)=2*(n/2)^2$. Please correct me if i am wrong.

• Fair enough. I hoped that this semantical problem would be integrated into an algebra ring, or something. Your reasoning is interesting, but I'm looking for a comprehensive answer. And the real problem are still odd $n$s (I expected that $f_{\text{max}}$ for them would be WAY harder in comparison). – Gregor Perčič Dec 2 '17 at 18:07
• The "most messed up" configuration is not unique: You can also move the first half of the things to the end, like cutting a deck of cards; this also gives $f=n^2/2$. – Rahul Dec 2 '17 at 18:08
• @Rahul that's why I wrote "one". – Nightgap Dec 2 '17 at 23:31
• Sorry, I wasn't correcting you, just offering a concrete example of non-uniqueness. – Rahul Dec 2 '17 at 23:58
• @Gregor Perčič note that the same argumentation can be applied if $n$ is odd. Then you have $2*(2+4+\ldots+(n-1))=4*(1+\ldots+(n-1)/2)=4*\frac{\frac{n-1}{2}\left(\frac{n-1}{2}+1\right)}{2}=\frac{1}{2}(n^2-1)$. – Nightgap Dec 3 '17 at 0:03