Insertion sort is highly efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.
But insertion sort is generally inefficient because insertion sort can only move data one bit at a time.
Hill sorting is named after its designer, Donald Shell, and the algorithm was published in 1959. Some older textbooks and reference manuals named the algorithm Shell-Metzner, which contains the name of Marlene Metzner Norton, but according to Metzner herself, "I did nothing for this algorithm, and my name should not appear in the algorithm." "
The basic idea of Hill sorting: first take an integer d1 less than n as the first increment, and divide all the records in the file into d1 groups. All records whose distance is a multiple of d1 are placed in the same group. First perform direct insertion sorting within each group; then, take the second increment d2 < d1 and repeat the above grouping and sorting until the increment dt=1(dt < dt-l< … < d2 < d1), that is, until all records are placed in the same group for direct insertion sort.
This method is essentially a grouped insertion method.
Example 1: