# What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

• What have you tried and where did you get stuck? Closely related questions: 1, 2. – Raphael Sep 2 '14 at 10:52

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted. This shows $n-k$ moves is necessary.