Minimum number of operations to sort a list.

Question

The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.

Answer 1

Let the original list be $a_1,a_2,\ldots,a_n$. Let $1 \le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.

Then the minimum number of operations you need to order that list is $k$.

Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.

Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.

Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.

OTOH, it can be done in $k$ moves: Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.

An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially

$L_0=[3,2|1,4]$.

We send the $3$ to the position it should have with regards to $1$ and $4$:

$L_1=[2|1,3,4]$

Finally, we send $2$ to the correct place:

$L_2=[|1,2,3,4]$

and the list is completely ordered!