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?

"ordered items preserve their order" goes for all (correct) sort algorithms, by definition. A "stable" sort means equal items preserve their order. — Blorgbeard, Oct 19 '17 at 22:04
Any sort is going to change the unequal items. What makes a sort stable is that it keeps equal items in the same relative order they were beforehand. (For example, sorting on a different column in a table will keep the rows within each category subsorted.) — chrylis -cautiouslyoptimistic-, Oct 19 '17 at 22:05
Related: https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important — Blorgbeard, Oct 19 '17 at 22:07
From what I can see with mental debugging the algorithm is not stable and hence wrong, it should be `> temp`. You should verify it with real debugging. — Oleg, Oct 19 '17 at 22:11
Tried debugging, ">=" changes the order whereas ">" seem to be working fine. There seem to be an error in the examle, I couldn't believe. — ITisha, Oct 19 '17 at 22:26
It happens ... . Sometimes the publisher or the author post fixes online. Check if it happened in this case and if not consider sending them an email. — Oleg, Oct 19 '17 at 22:30
You can do it [here](http://www.informit.com/store/data-structures-and-algorithms-in-java-9780672324536) it's possible you're the first one to notice. — Oleg, Oct 19 '17 at 22:40

score 4 · Accepted Answer · answered Oct 19 '17 at 22:51

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. :)

Do equal elements preserve their order in Insertion Sort algorithm?

1 Answers1