Insertion Sort

Insertion Sort -
Complexity
 Worst case  and Average case - O(n ^ 2) 
  Best case -  n-1  - In best case interestingly , the inner loop ( in code ahead ) executes only once as the element is in order ( increasing  or decreasing )


Example - 

import java.util.Arrays;


public class InsertionSort {
public static void main (String args[]){
char array[] = {'B','C','D','A','E','H','G','F' };


//print the unsorted sorted array
System.out.println("Unsorted array is - " + Arrays.toString(array));

//call function insertionSort
insertionSort(array);

//print the sorted array
System.out.println("Sorted array is - " + Arrays.toString(array));


}

//sorts the given array in " increasing order "
private static void insertionSort(char[] array) {
// save the length of array 
 final  int  LENGTH = array.length ;
 
 //loop through selecting second character as  first element is already sorted
 for(int i = 1 ; i < LENGTH ; ++i )
 {
 
 //place the array[i] in "order" with elements placed towards left of itself
 for( int j = i - 1 ; (j >=0 && array[j+1] < array[j]) ; --j )
 {
//xor-swap the elements to place at right order
 array[j+1] ^= array[j] ;
 array[j] ^= array[j+1] ;
 array[j+1] ^= array[j] ;
 
 
 }
 }
 
 
 

}
}