Is this equivalent to insertion sort?

Question

Say we have a 0-indexed sequence S, take S[0] and insert it in a place in S where the next value is higher than S[0] and the previous value is lower than S[0]. Formally, S[i] should be placed in such a place where S[i-1] < S[i] < S[i+1]. Continue in order on the list doing the same with every item. Remove the element from the list before putting it in the correct place. After one iteration over the list the list should be ordered. I recently had an exam and I forgot insertion sort (don't laugh) and I did it like this. However, my professor marked it wrong. The algorithm, as far as I know, does produce a sorted list.

Works like this on a list:

Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 0, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 6, 1, 7, 8, 10, 3, 9]
[0, 2, 4, 5, 1, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 10, 3, 9]
[0, 1, 2, 4, 5, 6, 7, 8, 3, 9, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Got [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Since every time an element is inserted into the list up to (n-1) numbers in the list may be moved and we must do this n times the algorithm should run in O(n^2) time.

I had a Python implementation but I misplaced it somehow. I'll try to write it again in a bit, but it's kinda tricky to implement. Any ideas?

The Python implementation is here: http://dpaste.com/hold/522232/. It was written by busy_beaver from reddit.com when it was discussed here http://www.reddit.com/r/compsci/comments/ejaaz/is_this_equivalent_to_insertion_sort/

Answer 1

It's a while since this was asked, but none of the other answers contains a proof that this bizarre algorithm does in fact sort the list. So here goes.

Suppose that the original list is v₁, v₂, ..., v_n. Then after i steps of the algorithm, I claim that the list looks like this:

w_1,1, w_1,2, ..., w_1,r(1), v_σ(1), w_2,1, ... w_2,r(2), v_σ(2), w_3,1 ... ... w_i,r(i), v_σ(i), ...

Where σ is the sorted permutation of v₁ to v_i and the w are elements v_j with j > i. In other words, v₁ to v_i are found in sorted order, possibly interleaved with other elements. And moreover, w_j,k ≤ v_j for every j and k. So each of the correctly sorted elements is preceded by a (possibly empty) block of elements less than or equal to it.

Here's a run of the algorithm, with the sorted elements in bold, and the preceding blocks of elements in italics (where non-empty). You can see that each block of italicised elements is less than the bold element that follows it.

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

If my claim is true, then the algorithm sorts, because after n steps all the v_i are in order, and there are no remaining elements to be interleaved. But is the claim really true?

Well, let's prove it by induction. It's certainly true when i = 0. Suppose it's true for i. Then when we run the (i + 1)st step, we pick v_i+1 and move it into the first position where it fits. It certainly passes over all v_j with j ≤ i and v_j < v_i+1 (since these are sorted by hypothesis, and each is preceded only by smaller-or-equal elements). It cannot pass over any v_j with j ≤ i and v_j ≥ v_i+1, because there's some position in the block before v_j where it will fit. So v_i+1 ends up sorted with respect to all v_j with j ≤ i. So it ends up somewhere in the block of elements before the next v_j, and since it ends up in the first such position, the condition on the blocks is preserved. QED.

However, I don't blame your professor for marking it wrong. If you're going to invent an algorithm that no-one's seen before, it's up to you to prove it correct!

(The algorithm needs a name, so I propose fitsort, because we put each element in the first place where it fits.)

Answer 2

Your algorithm seems to me very different from insertion sort. In particular, it's very easy to prove that insertion sort works correctly (at each stage, the first however-many elements in the array are correctly sorted; proof by induction; done), whereas for your algorithm it seems much more difficult to prove this and it's not obvious exactly what partially-sorted-ness property it guarantees at any given point in its processing.

Similarly, it's very easy to prove that insertion sort always does at most n steps (where by a "step" I mean putting one element in the right place), whereas if I've understood your algorithm correctly it doesn't advance the which-element-to-process-next pointer if it's just moved an element to the right (or, to put it differently, it may sometimes have to process an element more than once) so it's not so clear that your algorithm really does take O(n^2) time in the worst case.