The Insertion Sort Algorithm

The insertion sort algorithm is of O(n2) complexity. It divides an array into two sections: a sorted section and unsorted section. In each step of the algorithm the number is moved from unsorted section to sorted one, until the entire array is sorted.
This is a pseudo code:

Procedure: insertionSort(a)
- a: the array to sort
- a: sorted array in ascending order
1) For i = 1 to a.length:
a) Set element to a[i] and set j to i-1
b) While j >= 0 and a[j] > element:
i) Set a[j+1] to a[j]
ii) Decrement j by 1
c) Set a[j+1] to element
2) Return the sorted array

The Java code:

public static int[] insertionSort(int[] a) {
  for (int i = 1; i < a.length; i++) {
    int element = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > element) {
      a[j + 1] = a[j];
    a[j + 1] = element;
  return a;