# Minimal shift operations to sort an array

I have been stuck on this sorting problem for a while now:

Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting a value in an array to another position. For this problem however, you can only perform this shift operation on the first element in the array.

For example, let's say N = 4 and our array was [1,2,4,3].To sort this array we could perform the following shift operations:

[1,2,4,3] -> [2,4,1,3] -> [4,1,2,3] -> [1,2,3,4]

Thus, we would have to perform a minimum of 3 shift operations.

Any clues on how to approach this problem?

• Please add a reference to the original problem. Why is this important? Reasons. 1) Credit should be attributed. 2) The original problem might have other or more related materials, such as examples, hints, test cases and similar problems. 3) A reference is apt to motivate people. Jan 20 '19 at 4:40
• What have you tried so far? This site encourages you to show your thoughts or partial progress toward solving the problems. People could then make the answers more helpful for you and for future readers. Jan 20 '19 at 4:41

The number of shifts this takes is $$n -k$$ where $$k$$ is the length of the longest increasing suffix of the input.