Unusual Sorting Technique? Is It Effective?

I claim that if the array has $n$ elements and the longest increasing subsequence has $m$ elements, then we need to do the operation $n-m$ times and no more.

To see that we need $n-m$ operations, consider the elements that we don't choose for any of the operations. They are undisturbed, and thus their relative positions are the same; if an element $x$ is earlier than element $y$ and we never pick either of them, then in the resulting array we will also have $x$ earlier than $y$ . Suppose we take $k$ operations with $k < n-m$ . Then there are $n-k$ elements that are untouched. But because the longest increasing subsequence has length $m < n-k$ , the untouched elements cannot be an increasing subsequence. That is, there are two untouched elements $x$ and $y$ such that $x$ is earlier than $y$ but $x > y$ . At the resulting array, $x$ is again earlier than $y$ , and $x > y$ , so the array is not sorted.

To see that $n-m$ operations are enough, induct backwards from $m = n, n-1, n-2, \ldots, 1$ . The base case $m = n$ is trivial; the longest increasing subsequence has $n$ elements, or in other words the entire array. Thus the array is already sorted, and so we need $0 = n-m$ operations, as claimed.

For the inductive case, suppose that we have proven the claim for $m = m_0$ . For $m = m_0 - 1$ , take any increasing subsequence of length $m$ . (There must be one, because we assume $m$ is the length of the longest increasing subsequence. There can be more than one; pick any of them.) Now pick any element not in this subsequence, and insert it to the correct relative position. For example, in (3, 1, 2, 5, 4), one increasing subsequence is (1, 2, 4). We can take the 3 and insert it to its correct relative position, between 2 and 4. That is, we now have either (1, 2, 3, 5, 4) or (1, 2, 5, 3, 4); both are okay. Now the length of the longest increasing subsequence increases by one; the subsequence we picked along with the element we did an operation with (in the above, the (1, 2, 4) and the 3), so we have a longest increasing subsequence of length $(m_0 - 1) + 1 = m_0$ . By inductive hypothesis, this can be done in $n - m_0$ operations. We did one extra operation, so in total we did it in $n - m_0 + 1 = n - (m_0 - 1) = n-m$ operations, proving the claim.

Now that we have that claim, just note that $n = 12$ . $m$ can be determined in various ways; there is an $O(n \lg n)$ algorithm, but because $n$ is small enough, the naive $O(n \cdot 2^n)$ algorithm of checking every possible subsequence is enough. We obtain $m = 6$ , with the subsequence (1, 4, 7, 8, 13, 14). Thus we need $n-m = 12-6 = \boxed{6}$ operations.

I used just logic

The max no. Of elements that are already in increasing order is 6, namely 1,4,7,8,13,14. So we will remove the remaining 6 elements and place them in their positions. 6 steps required for this.