Thoughts on best practices
Method signature should be void and should simply return the modified original array. Again, is this behavior better / more-expected? My argument against this is that maybe it could lead to some unexpected behavior if the user does not expected the original array to be modified? Or unexpected behavior down the road if the user forgets that the returned array has been modified. That being said, with proper documentation, this could be avoided.
This is a variant of the Single Responsibility Principle. Your method is supposed to sort something. Should it also copy something? Or only sort? Note that there is no way to sort in place with your version (except to copy back over the original array). But with a sort-in-place version, you can easily duplicate your method's functionality:
int[] sorted = unsorted.clone();
InPlaceSorter.sort(sorted);
Now we have unsorted, which is the original array, and sorted, which is a new sorted version of the original array.
Documentation and the fact that saying
int[] sorted = InPlaceSorter.sort(unsorted);
will produce a compiler error should be enough to make clear that the array is being modified.
By contrast, calling
InsertionSorter.sort(unsorted);
without assigning the result will silently not do anything useful. So I'd find your version riskier, as it doesn't warn when someone tries to do the wrong thing.
If you do stick to your original version, consider changing the name to make it clearer. E.g. generateSortedCopyOf. If I read that, I expect it to return a copy without modifying the original. And I wouldn't try calling it to do a sort-in-place.
One uses double for-loops vs. a for-loop and a while-loop. Is the double for-loop more readable?
Personally, I don't have a strong feeling about this one way or the other. All for loops can be written as while loops and sometimes I find it more convenient.
int j = i - 1;
int numberToInsert = sorted[i];
while (j >= 0 && numberToInsert < sorted[j]) {
sorted[j + 1] = sorted[j];
sorted[j] = numberToInsert;
j--;
}
But this does translate nicely to a for loop.
int numberToInsert = sorted[i];
for (int j = i - 1; j >= 0 && numberToInsert < sorted[j]; j--) {
sorted[j + 1] = sorted[j];
sorted[j] = numberToInsert;
}
No gymnastics required to fit it into the for pattern. I think that I'd vote for this solution as simpler in this case. But see ahead.
Optimizations
This solution does more assignments than needed. Consider
int j = i - 1;
int numberToInsert = sorted[i];
for (; j >= 0 && numberToInsert < sorted[j]; j--) {
sorted[j + 1] = sorted[j];
}
j++;
sorted[j] = numberToInsert;
Now it's not nearly as obvious that this should be a for loop.
int j = i - 1;
int numberToInsert = sorted[i];
while (j >= 0 && numberToInsert < sorted[j]) {
sorted[j + 1] = sorted[j];
j--;
}
j++;
sorted[j] = numberToInsert;
Either way though, this could save you a bunch of assignments at the expense of always doing an assignment (we can check that i != j if we want to avoid that useless assignment). But looking at this, we have another option:
int j = i - 1;
int numberToInsert = sorted[i];
while (j >= 0 && numberToInsert < sorted[j]) {
j--;
}
j++;
if (j != i) {
System.arraycopy(sorted, j, sorted, j + 1, i - j);
sorted[j] = numberToInsert;
}
Now we allow the Java compiler to do any optimizations that System.arraycopy allows. At worst this should be the same as the original.
And we might do even better if we take advantage of the sorted portion of the array.
int numberToInsert = sorted[i];
int j = Math.abs(1 + Arrays.binarySearch(sorted, 0, i - 1, numberToInsert));
if (j != i) {
System.arraycopy(sorted, j, sorted, j + 1, i - j);
sorted[j] = numberToInsert;
}
Of course, one of the benefits of an insertion sort is its simplicity. This replaces two things we originally did in a single loop with two system calls. That may not be faster in some cases. In particular, consider the case of an already sorted list. The original algorithm runs in \$O(n)\$ time in that case, as the inner loop simply doesn't iterate. This version would run in \$O(n \log n)\$ because binarySearch is a logarithmic operation.
Note: adding one to the binarySearch result and taking the absolute value always gives the insertion point. This is because a positive result is the current location of the element, and we want to insert after the current location in case of duplicates (technically we want to insert after the last duplicate, but I didn't add that logic); and a negative result is one less than the insertion point.
Another issue is that the original version might parallelize better. One core can do comparisons while the other core writes values. Or maybe the compiler optimizes binarySearch and arraycopy better. You'd have to test to see, and you might get different results on different platforms.
