Insertion Sort in Java

Insertion sort is a simple sorting algorithm that works by building a final sorted array one item at a time. It is a comparison-based algorithm in which the array is divided into two parts, the sorted part, and the unsorted part. In each iteration, the algorithm removes one element from the unsorted part, finds the location it belongs within the sorted part and inserts it there. This process is repeated until the unsorted part becomes empty.

Here is an example implementation of the Insertion Sort algorithm in Java:

```public class InsertionSort {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 9, 1};
int n = arr.length;

for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}

// Print the sorted array
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

In this example, the algorithm takes an array arr and sorts it using the insertion sort technique. The for loop starts from the second element of the array, as the first element is considered already sorted. For each element, the algorithm checks the previous elements in the array to find the correct position to insert the current element. The while loop performs this task, and the for loop prints the sorted array.