Insertion Sort

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain.

Example: The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}.
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 7 4 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 7 9 5 2 6 1
3 4 5 7 9 2 6 1
2 3 4 5 7 9 6 1
2 3 4 5 6 7 9 1
1 2 3 4 5 6 7 9

Key points:
   1) Simple implementation
   2) Efficient for (quite) small data sets
   3) Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n +          d), where d is the number of inversions
   4)More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort        or bubble sort; the best case (nearly sorted input) is O(n)
   5)Stable; i.e., does not change the relative order of elements with equal keys
   6)In-place; i.e., only requires a constant amount O(1) of additional memory space
   7)Online; i.e., can sort a list as it receives it

class InsertionSort{
//method for insertion sort
public static void insertionSort(int []a, int size){
int temp;

for(int i = 1; i<size; i++){
for(int j = i; j > 0; j--){
if(a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}

public static void main(String []args){
int a[] = {5,1, 4, 2, 8};
insertionSort(a, a.length);
System.out.println("elements of array after sorting..."+java.util.Arrays.toString(a));
}
}

Time Complexity  : O(N^2) worst and average case
Space Complexity : O(1)