Anyone have a sort algorithm optimized for very slow write operations?

Question

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

O=Move an item X to index Y. The elements on subsequent positions are shifted 1 position.

The algorithm must be optimized for the least possible number of operations O. Read operations are infinitely cheaper than write operations. Temporary helper lists are also cheap.

Edit: It might be more correct to call it a linked list, because of its behaviour, although the implementation is hidden for me.

Background:

The thing is 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. You can assume the sorting program (the client) has a copy of the list in memory before starting, so there is no need to perform read operations against the service - only write. You can of course also do any amount of temporary list actions locally before performing the service calls, including duplicating the list or using existing .NET sort functions.

How do I proceed here? Is there a known algorithm I can use here?

Failed attempt:

I have already implemented a dumb algorithm, but it is not optimal for all cases. It works well when the list is like this:

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

It goes like this:

1. Is list sorted? No
2. Find element that belongs at position 0: "1"
3. Move Element "1" to position 0
4. (New list state A1: [1,2,3,4,5,6,7,8,9])
5. Is list sorted? Yes. End

...But when the list is like this, I get into trouble:

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

1. Is list sorted? No
2. Find element that belongs at position 0: "1"
3. Move Element "1" to position 0
4. (New list state B1: [1,9,2,3,4,5,6,7,8])
5. Is list sorted? No
6. Find element that belongs at position 1: "2"
7. Move Element "2" to position 1
8. (New list state B2: [1,2,9,3,4,5,6,7,8])
9. ...you can see where I'm going here...

Answer 1

Compute the longest increasing subsequence of the array. Perform a write operation for each element that is not present in the sequence.

EDIT: Adding an example

Let the numbers in the input array be 1 3 2 7 4 8 6 5 9. A longest increasing sequence is 1 2 4 6 9. When computing this sequence store the indexes of the elements that occur in the sequence. Then it is straightforward to travel through the original array and find the elements not present in the sequence. In this case they are 3 7 8 5. For each of these elements perform a write operation that places them in the appropriate position. So the sequence of modifications of the array would be:

1 2 3 7 4 8 6 5 9 (after writing 3 to appropriate position)
1 2 3 4 8 6 7 5 9 (after writing 7 to appropriate position)
1 2 3 4 6 7 5 8 9 (after writing 8 to appropriate position)
1 2 3 4 5 6 7 8 9 (after writing 5 to appropriate position)

Answer 2

Sort the array locally. Keep a copy of the original.

Compute the optimal edit sequence between the original array and the sorted version using LCS distance; that's the variant of Levenshtein distance where substitutions are not allowed. A simplified version of the dynamic programming algorithm for Levenshtein can be used to compute LCS distance. Look at the source code for programs such as diff to see how the edit sequence can be obtained from the dynamic programming table.

You now have an edit sequence, meaning a list of insertions and deletions to be performed to transform the original array into the sorted version. Perform the insertions. (You can skip the deletions since they'll be performed by your operation O, but be aware that indices into the arrays change because of that, so you'll have to compensate for that.)