Sorting algorithms can be roughly divided into the following categories

  1. Insert sort: direct insert sort, half-broken insert sort, Hill sort
  2. Select class sort: simple select sort, heap sort
  3. Swap class sort: bubble sort, quick sort

This paper introduces the basic implementation idea of shell sort. Shell sort is also called “disminishing increment sort”. It is based on insertion sort, which shows the importance of increment in Hill sort. It is a more efficient version of the improved simple insertion sort, and it was one of the first algorithms to break O(n2). It differs from insertion sort in that it compares distant elements first.

Time complexity of Hill sort

The time complexity of Hill sort is related to the selection of increment H. For example, when increment H =1, it is equivalent to an insertion sort, and the time complexity is O(N²). However, the time complexity of Hill sort of Hibbard increment is O(N3/2), so the time complexity of Hill sort cannot be accurately stated, while the space complexity of Hill sort is O(1). Visible incremental selection of hill sort

Delta selection problem

The problem has been debated by the best minds for decades with no result. Herbert Schildt, The author of “C: The Complete Reference”, says:

  1. Never use a power of two as a increment
  2. The last increment must be 1(duh!)
  3. He recommended: 9, 5, 3, 1
Extension: Insert sort

1. Start with the second value in the array and compare it with the previous value. If the value is larger or smaller than the previous value, make them swap places.

For example, if there are 5 numbers 8,15,20,45,17,17 are smaller than 45 and need to be swapped, but 17 is also smaller than 20 and need to be swapped. When there is no need to swap with 15, it means that there is no need to compare with the data before 15. You definitely don’t need to swap, because the data on the front is sorted.

3. Repeat Step 2 until all data is sorted.