It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

After expanding the swap operation in-place as x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x (where x is a temporary variable), a slightly faster version can be produced that moves A[i] to its position in one go and only performs one assignment in the inner loop body:[1] The new inner loop shifts elements to the right to clear a spot for x = A[i].

The recursion just replaces the outer loop, calling itself and storing successively smaller values of n on the stack until n equals 0, where the function then returns up the call chain to execute the code after each recursive call starting with n equal to 1, with n increasing by 1 as each instance of the function returns to the prior instance.

It does not make the code any shorter, it also does not reduce the execution time, but it increases the additional memory consumption from O(1) to O(N) (at the deepest level of recursion the stack contains N references to the A array, each with accompanying value of variable n from N down to 1).

The simplest worst case input is an array sorted in reverse order.

In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element.

The key that was moved (or left in place because it was the biggest yet considered) in the previous step is marked with an asterisk.

The sorting algorithm compares elements separated by a distance that decreases on each pass.

[5][6] If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance.

[7] The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion.

[7] The number of swaps can be reduced by calculating the position of multiple elements before moving them.

If a more sophisticated data structure (e.g., heap or binary tree) is used, the time required for searching and insertion can be reduced significantly; this is the essence of heap sort and binary tree sort.

The authors show that this sorting algorithm runs with high probability in O(n log n) time.

A simpler recursive method rebuilds the list each time (rather than splicing) and can use O(n) stack space.