What is the difference between shuttle sorting and insert sorting

If we have an array of elements a and we need to move the element a[i] to the left in the position j (j < i), then you can do this in two ways:

• Method 1. Save the value of a[i] to the side. Move all elements with indexes [i, j) to the right one step, then write the original value a[i] to the" freed " cell a[i].

• Method 2. Swap the elements a[i] and a[i - 1]. Then swap the elements a[i - 1] and a[i - 2]. etc. and until we exchange the pair a[j+1] and a[j]. It is easy to see that the result of such manipulation coincides with the option 1.

Insert sorting first scans the left side of the array to find the correct j location for the next a[i] element. After that, using method 1, the element a[i] is placed in the correct place j.

Shuttle sorting immediately starts performing manipulations of method 2, on the fly checking if whether the a[i] element has already reached its correct position on the left side of the array.

The only more or less tangible difference between insertion sorting and shuttle sorting is that the first first runs through the left side of the array to find the insertion location, and then moves the new element (which actually results in another pass through the left side of the array).

A shuttle sorting combines and location search inserts, and actually moving elements in a single pass along the left side of the array.

If desired, you can implement sorting by inserts, but to move the element to a new location, use method 2. In such a situation, the only difference between these sorts is that the insertion sort looks for the correct place for the element in advance of (before executing method 2), and the shuttle sort looks for the correct place for the element on the on the fly (while executing method 2).