Do equal elements set their order in the insertion sorting algorithm?

Question

Robert Lafo's book, Data Structures and Algorithms in Java, says that Sorting Sorting is a stable algorithm. This means that equal elements maintain their order.

Here is an example from a 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 loop, whilewe go left and look for a place for the variable temp. And even if a[in - 1] == temp, we still move one step to the left and insert tmpbefore a[in - 1], and in the original array tmp, to the right of a[in - 1].

After sorting, the order of the array elements has changed. How stable is this algorithm then? Shouldn't it be a[in - 1] > tempinstead a[in - 1] >= temp?

Maybe I'm just wrong and I don’t see anything obvious?

Answer 1

. " " . .

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

, A [i] > . "[in-1] > temp". , .:)