Code fragment illustrating the basic insertion sort algorithm. for i = 1,...,n { // Insert each element in turn, except the first. new_a = a(i); // The new element to be inserted. j = i-1; // j runs through the elements already inserted and in order. // Move the sorted elements to the right one by one until // you find the spot for new_a. while (a(j) > new_a ) { // Elements larger than new_a are moved over. a(j+1) = a(j); j = j - 1; } a(j+1) = new_a; // This is where new_a goes. } // All done!