Performs an insertion sort by splitting the list into a sorted and an unsorted portion. Each node is then inserted one-by-one into the sorted portion.
public void insertionSort() {
int n = array.getLength();
for (int i = 1; i < n; ++i) {
int key = array[i];
int j = i - 1;
/* Move elements of array[0..i-1], that are greater than key, to one position ahead of their current position */
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
Helper method to insert a node into its proper location in a sorted linked chain.
@param nodeToInsert: node to add to sorted section of list
public void insertIntoSorted(Node<T> nodeToInsert) {
// implementation
}