C# Hill sort

C#Hill Sorting

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
namespace Sort  
{  
    class ShellSorter  
    {  
        public static int[] Sort(int[] a)  
        {  
            ShellSort(a);  
            return  a;  
        }  
        public static void ShellSort(int[] myArray)  
        {  
            int i, j, increment;  
            int temp;  
            for (increment = myArray.Length / 2; increment > 0; increment /= 2)  
            {  
                for (i = increment; i < myArray.Length; i++)  
                {  
                    temp = myArray[i];  
                    for (j = i; j >= increment; j -= increment)  
                    {  
                        if (temp < myArray[j - increment])  
                            myArray[j] = myArray[j - increment];  
                        else  
                            break;  
                    }  
                    myArray[j] = temp;  
                }  
            }  
        }  
    }  
}

Hill sorting is an improvement on the direct insertion sorting algorithm. Its main idea is to first divide the entire sorted sequence into several subsequences, and perform direct insertion sorting on the subsequences. , and then perform a direct insertion sort on all the arrays when they are basically in order. This is used to form a new ordered sequence. The general division method is that the distance between two elements is d=n/2, n/4, n/8...and so on.
1. Basic idea:
Divide the entire data elements to be sorted into several groups, and use the direct insertion method to sort the data elements in the same group; the number of groups is gradually reduced, and when all data elements are completed The sorting process ends after sorting within a group.
2. Skills:
The composition of the group is not simply "divided segment by segment", but the records separated by a certain increment dk are formed into a group, and the increment dk is shortened step by step (for example, 5 is taken in sequence, 3,1) until dk=1.
3. Advantages:
If the elements with small key values ​​can be moved forward quickly, and if the sequence is basically in order, then direct insertion sorting can be used, and the time efficiency will be much higher.

Example one:

Example two: