← binarysearch(A[j], S, 2^(i − 1)) insert A[j] at S[ins] Here, binarysearch(el, A, k) performs binary search in the first elements of , skipping over gaps, to find a place where to locate element . Insertion should favor gaps over filled-in elements. References External links Gapped Insertion Sort Sorting algorithms Comparison sorts Stable sorts Online sorts