# Insertion sort algorithm in Java

I have tested this code and it yields the expected outputs, but I want to verify if I have applied insertion sort algorithm correctly or not.

 import java.util.*;
public class InsertionSort
{
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

static void sorter(int arr[])
{

int hole;
int n = arr.length;
if(n>=2)
{
for(int i = 1; i<n ; i++)
{
hole = i;
inner:
for(int j = i-1; j>=0; j--)
{
if(arr[j]> arr[hole])
{
swap(arr, j, hole);
hole = j;
}
else
break inner;
}
}
}
System.out.println(Arrays.toString(arr));
}
}

• Do you want to ascertain correctness or Elegance? Correctness can be found by tests. – Sid Feb 16 '19 at 9:45
• You should follow the Java Naming Conventions: variable names always start with lowercase. Arr should be arr. – MC Emperor Feb 16 '19 at 9:46
• @MCEmperor Sure, fixing that right now. – Archer Feb 16 '19 at 9:47
• You can check for such answers online geeksforgeeks.org/insertion-sort – Abdul Wasey Feb 16 '19 at 9:48
• It's correct, but it's far from good code. There is no need for n as intermediate variable, if (n>=2) is redundant, because it will just loop once in this case. The label inner is redundant in this case. And in general, if you ever feel you need to use a label in Java, you should restructure your code. And, finally, printing the result should not be done in the sort method. – wvdz Feb 16 '19 at 10:04

### Labeled loops

You say

                        break inner;


But that's not necessary. The inner loop is already the innermost loop. You could just say break;.

And frankly, you could have just said

                for (int j = i-1; j >= 0 && arr[j] > arr[hole]; j--)


No break or internal if needed.

But that's not the question you really wanted answered.

### Insertion sort?

It's similar to an insertion sort. Your insertion method is a bit odd though. Normally insertion sort would find the insertion point and then move the elements after that. You're bubbling the current value forward.

Consider

int j = i - 1;
while (j >= 0 && numbers[j] < numbers[i]) {
j--;
}

int temp = numbers[i];
for (int k = i; k > j; k--) {
numbers[k] = numbers[k - 1];
}

numbers[j] = temp;


### Naming

I prefer a descriptive name like numbers to a generic abbreviation like arr. At minimum, it should be array. But I prefer numbers.

    static void sorter(int arr[])


As a general rule, we name classes and objects with noun names. Methods get verb names. So

    static void sort(int[] numbers) {


In Java, we also normally write arrays as int[] name not int name[].

You could name the class

class InsertionSorter {


Although in this case InsertionSort can be used as a noun.

### Wildcard imports

import java.util.*;


The general policy is to import one class at a time, not a wildcard group. That's especially true here, since it's not clear that you are using any java.util classes.

### Mixing logic and display

It's generally agreed that it is better to return the data and display it separately. Since you are sorting in place, that could just look like

InsertionSort.sort(numbers);
System.out.println(Arrays.toString(numbers));


### Declare at initialization

You have

                hole = i;


You could do

                int hole = i;


It's generally considered best practice to declare variables as late as possible. You don't use hole outside the loop or across iterations, so there's no need to declare it outside the loop.

### Redundant logic

        if(n>=2)
{
for(int i = 1; i<n ; i++)


If n is 1 or less then 1 < n will be false and it won't enter the loop.

And you don't need n. You can just say numbers.length whenever you need that value.

### Standard methods

You could also replace these two loops with Java standard methods.

        int insertionPoint = Arrays.binarySearch(numbers, 0, i, numbers[i]);
if (insertionPoint < 0) {
insertionPoint = -insertionPoint - 1;
}

int temp = numbers[i];
System.arraycopy(numbers, insertionPoint, numbers, insertionPoint + 1, i - insertionPoint);
numbers[insertionPoint] = temp;


Of course, it's possible that you were trying to avoid standard methods. After all, Arrays.sort would solve this problem without additional coding.