I need a sorting algorithm which operates on a single, pre-populated array, and which is limited to perform only one operation:

-Move an item to position P, pushing all elements from position P+X to position P+X+1 (X => 0)

The algorithm must be optimized for the least possible number of operations (obviously).

Why? I'm working against a Google API which only allows me to perform this operation on their lists. The operation is a web service call. I want to minimize the number of calls.

Does this algorithm exist and have a name? Anyone want to give it a shot on a solution?

I have already implemented a dumb algorithm, but it is not optimal. Example:

List1 = [2,3,4,5,6,7,8,9,1]

Zero elements are in their correct place. A smart algorithm would move the last item to index 0 (zero), effectively pushing all other items one index down and the sorting is complete. MY algorithm checks the element at position 0, finds out it belongs in position 1 and puts it there, causing the list to now be in this state:

List1 = [3,2,4,5,6,7,8,9,1]

..I don't think I need to go on