Do equal elements preserve their order in Insertion Sort algorithm?

Question

In the "Data Structures and Algorithms in Java" book of Robert Lafore it is stated that the Insertion Sort is a stable algorithm. Which means that equal items preserve their order.

Here is the example from the book:

public void insertionSort() {
    int in, out;
    for (out = 1; out < nElems; out++) // out is dividing line
    {
        long temp = a[out]; // remove marked item
        in = out; // start shifts at out
        while (in > 0 && a[in - 1] >= temp) // until one is smaller,
        {
            a[in] = a[in - 1]; // shift item right,
            --in; // go left one position
        }
        a[in] = temp; // insert marked item
    } // end for
} // end insertionSort()

In the while cycle we are going left and seeking for a place for temp variable. And even if a[in - 1] == temp, we still move one step left and insert tmp before a[in - 1] while in the original array tmp was to the right of a[in - 1].

The order of array elements changed after the sorting. How is this algorithm is stable then? Shouldn't there just be a[in - 1] > temp instead of a[in - 1] >= temp?

Maybe i'm just making a mistake and don't see something obvious?

Answer 1

You are absolutely right. This here is a snippet of the Insertion Sort Algorithm from the popular book "Introduction to Algorithms" by Thomas H. Cormen.

INSERTION-SORT(A)
1. for j=2 to A.length
2. key = A[j]
3. // Insert A[j] into the sorted sequence A[1..j-1].
4. i = j-1
5. while i > 0 and A[i] > key
6. A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key

As you can see, A[i] > key is correct. It should be "a[in - 1] > temp" in your case. Good job at noticing it. :)