Sort and insert sort
You can implement insertion sort as a series of comparisons and swaps of adjacent items. This makes it "stable". Instead, Shell sorts and swaps items that are far from each other. This makes it faster.
I suppose your confusion comes from the fact that shell sort can be implemented as multiple nestings applied to different subsets of the data. Note that these subsets are composed of non-contiguous elements of the data sequence.
See Wikipedia for details; -)
source to share
Shell sort is a generic version of Insert Sort . The basic principle is the same for both algorithms. You have a sorted sequence of length n , and you insert an unsorted element into it - and you end up with a long ordered sequence of n + 1 elements .
The difference is as follows: while insertion sort works with only one sequence (initially the first element of the array) and expands it (using the next element). However, the shell sort has a decreasing increment, which means that there is a gap between the items being compared (initially n / 2 ). Hence, there are n / 2 sequences for sorting using insert sort. At each step, the increment is compressed (often simply divided by 2.2 ), and the number of sequences decreases. In the last step, there is no space and the algorithm degenerates into a simple insertion sort.
Because of the decreasing increment, the large and small items are moved quickly to fix part of the array, and in the last step are sorted by insertion sort very quickly. This results in a reduction in time complexity of O (n ^ (4/3))
source to share
insertion sort is a simple, in-place, O (N ^ 2) sort. Shell sort is a little harder and harder to understand, and somewhere around O (N ^ (5/4)). Check the links for examples - it should be easy to see the difference.
source to share