Insertion Sort

Insertion Sort is a sorting algorithm similar to Selection Sort done by looping through each individual element from left to right and inserting it in a spot to the left that would keep all the elements left of the current element in sorted order. See below for an implementation of Insertion Sort:

public static void insertionSort(int[] elements) {

// Loop through all elements from left to right

for (int j = 1; j < elements.length; j++) {

// Make a third hand variable with the current index

int temp = elements[j];

// The index for a possible insertion position

int possibleIndex = j;

// Loop through the left side to find the insertion position

while (possibleIndex > 0 && temp < elements[possibleIndex - 1]) {

elements[possibleIndex] = elements[possibleIndex - 1];

possibleIndex--; // Keep searching left

}

// After we find the insertion position, insert the third hand into

// the insertion position found

elements[possibleIndex] = temp;

}

}

Implementation by AP CollegeBoard

Comments by Jimmy Liu