Insertion Sort

Insertion sort, as the name says works by inserting the element in proper position of a sorted list. This works by first marking a element in the array as a markedElement. All the elements before the markedElement will be sorted. All the elememts to the right of the markedElement will be unsorted.
Sorting proceeds by comparing the markedElement with the sorted elements, inserting the markedElement in the correct position based on the comparision.

In Detail: For example, if we consider an array of N elements, to startwith, we will consider the second element as the markedElement. So, to the left of the markedElement is only one element, which we consider as sorted.(Remember, elements towards left of the markedElement is considered as sorted).
We proceed by comparing the markedElement with the largest element(rightmost element) in the sorted list. Upon each pass, the size of the sorted sub-list will increase.

Best case sorting is when the elements are already sorted. Then, the sort has a complexity of O(N). Worst case is when a array is sorted in the reverse order. Thats when the complexity will be quadratic O(N2).
However, insertion sort is considered as a quickest way to sort small data. It is considered quicker than quickSort for small data. It is not a good solution for sorting large data.



InsertionSort Program

package com.algoWork.sort;

import java.util.ArrayList;
import java.util.List;

public class InsertionSort<T extends Comparable<T>> {

    public void sort(List<T> arrayElements) {

        // Iterate over the arrayElements from second element
        for (int i = 1; i < arrayElements.size(); i++) {

            // consider the secondElement as the markedElement
            T markedElement = arrayElements.get(i);
            // Get the index of the markedElement
            int markedElementIndex = i;
            // Keep shifting the elements in the subList towards right until you
            // find the correct position to insert the markedElement. This
            // Comparison will be done till markedIndex is greater than 0 and
            // markedElement is less that the compared element in the subList.

            while (markedElementIndex > 0
                    && markedElement.compareTo(arrayElements
                            .get(markedElementIndex - 1)) < 0) {
                arrayElements.set(markedElementIndex,
                        arrayElements.get(markedElementIndex - 1));
                markedElementIndex--;
            }
            // At the end of the loop, correct position to insert the
            // markedElement in the subList will be found and insert the element
            // in that position.
            arrayElements.set(markedElementIndex, markedElement);
        }

    }

}

Complexity: Complexity of this sorting mechanism is O(N2). But this is twice as fast compared to Bubble sort and Selection sort.

Reference: Data Structures and Algorithms 2nd Edition Robert Lafore