Insertion Sort Implementation

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than the more advanced algorithms such as quicksort, heapsort, or merge sort, but it has various advantages:

• Simple to implement
• Efficient on (quite) small data sets
• Efficient on data sets which are already substantially sorted
• More efficient in practice than most other simple O(n2) algorithms such as selection sort or bubble sort: the average time is n2/4 and it is linear in the best case
• Stable (does not change the relative order of elements with equal keys)
• In-place (only requires a constant amount O(1) of extra memory space)
• It is an online algorithm, in that it can sort a list as it receives it.
  

In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm.

The following method shows how to implement insertion sort with Java:

public static void insertionSort( Comparable [ ] a )

{

for( int p = 1; p <>

{

Comparable tmp = a[ p ];

int j = p;

for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) <>

a[ j ] = a[ j - 1 ];

a[ j ] = tmp;

}

}

Source: java-tips.org