In-Place Insertion Sort Purpose

Implementation for in-place Insertion Sort.

Discussion

The idea is to start with the second element in the input array (in the single element case, it's already sorted).

Moving backwards, compare the value against each prior element in the array until


You reach the beginning of the array
You find an element that is &lt;= your value


As you continue backwards, move the last value you considered to the next index in the array.

Then repeat the same steps for the third, fourth, etc. elements, if they exist.

Implementation



public class InsertionSorter {
    public static void sort(int[] values) {
        for (int index = 1; index &lt; values.length; index++) {
            int value = values[index];
            int nextIndex = index - 1;
            while (nextIndex &gt;= 0 &amp;&amp; values[nextIndex] &gt; value) {
                values[nextIndex + 1] = values[nextIndex];
                nextIndex--;
            }
            values[nextIndex + 1] = value;
        }
    }
}
Naming index and nextIndex as i and j would have been OK.

There are no comments, which is not necessarily a problem. But a one-line javadoc for the function would be helpful. I know, I know, from the signature it's kind of obvious, but still. For example, what if caller passes in null? Well, we throw a fatal exception, and that seems appropriate, caller gets what he deserves, he violated the contract spelled out in the javadoc. But only if there is a javadoc explaining the caller's responsibility.

The inner while loop would be more naturally expressed as a for loop.

The inner while loop might become a helper function. Then you'd have the opportunity to give it an informative name, perhaps copy.

That said, overall the function as written is reasonably clear.