Shell Sort

Shell Sort is an efficient improved version of insertion sort, proposed by Donald Shell in 1959.

The core idea of Shell sort isBy dividing the original list into multiple subsequences, first performing insertion sort on each subsequence, then gradually reducing the interval between subsequences, and finally performing a standard insertion sort on the entire list.This method allows elements to move across large spans, thereby eliminating a large number of inversions in the early stages and significantly improving sorting efficiency.

Imagine sorting a shuffled deck of playing cards. Insertion sort is like picking up cards one by one and inserting each into the correct position in the already sorted hand. Shell sort, on the other hand, is like first drawing out every few cards to form a small pile and sorting it, then reducing the drawing interval and repeating the process. When the interval is reduced to 1, it becomes standard insertion sort, but by then the entire sequence is already basically ordered, so the final insertion sort will be very fast.

How it works

The key to Shell sort lies in a so-calledIncrement sequenceThe concept. The increment sequence determines the interval for dividing subsequences each time. The algorithm performs multiple rounds of sorting on the list according to a gradually decreasing increment sequence.

Algorithm steps

  1. Select the increment sequence.Determine a sequence of integers from large to small, and the last increment must be 1. The most commonly used initial increment is half the array length, and then it is halved each time.
  2. Group by increment: for the current incrementgap, divide the entire list intogapsubsequences. Each subsequence consists of all elements with an interval ofgapThe element composition.
  3. perform insertion sort on the subsequencesPerform insertion sort on each subsequence separately.
  4. Reduce the incrementObtain a new, smaller increment, and repeat steps 2 and 3.
  5. Final sortWhen the increment is reduced to 1, perform a standard insertion sort on the entire list; at this point the list is already basically ordered, so sorting is completed quickly.

Applicability

The time complexity of Shell sort isO(n^(1.3-2)), and the space complexity is of constant orderO(1). Shell sort is not as fast asO(n(logn))the quicksort algorithm is fast, so it performs well for medium-sized scales, but it is not the optimal choice for sorting very large data sets. In short, compared to the ordinaryO(n^2 )algorithms with that time complexity are much faster.

Process Diagram

The purpose of Shell sort is to improve insertion sort for faster speed. It swaps non-adjacent elements to sort portions of the array, and finally uses insertion sort to sort the locally ordered array.

Here we choose the incrementgap=length/2, reduce the increment togap = gap/2method, using the sequence{n/2,(n/2)/2...1}to represent.

As shown in the example:

(1) The first pass with the initial incrementgap = length/2 = 4

(2) The second pass, the increment is reduced to 2

(3) The third pass, the increment is reduced to 1, obtaining the final sorted result

Java example code

Source code package download:Download

The innermost loop is in fact insertion sort:

ShellSort.java file code:

public class ShellSort {
    // Core code --- start
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
    // Core code --- end
    public static void main(String[] args) {

        int N = 2000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
        ShellSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

Python algorithm implementation

We will use Python to implement Shell sort, and adopt the most common increment setting (Shell's original sequence):gap = n // 2, and continue togapperform integer division by 2, untilgapis 1.

Example

def shell_sort(arr):
    """
Use the Shell sort algorithm to sort the list in ascending order in place.
   
Parameters:
arr (list): The list to be sorted.
   
Returns:
list: The sorted list (modified in place, also returned).
    """
    n = len(arr)
    # Set the initial increment gap to half the length of the array
    gap = n // 2
   
    # Loop until gap is reduced to 0
    while gap > 0:
        # Starting from gap, perform "insertion sort" on each element
        # Note: Here i goes from gap to n-1, iterating over all elements
        for i in range(gap, n):
            # Save arr[i] to a temporary variable temp
            temp = arr[i]
            j = i
            # Perform insertion sort on the subsequence under the current gap
            # If the preceding element in the same subsequence is greater than temp, move it backward
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            # Insert temp into the correct position
            arr[j] = temp
        # Reduce the increment, e.g., halve the gap
        gap //= 2
   
    return arr

# Test code
if __name__ == "__main__":
    # Test data 1: random shuffled order
    test_array = [8, 3, 5, 1, 4, 2, 7, 6]
    print("Before sorting:", test_array)
    sorted_array = shell_sort(test_array.copy()) # Use copy to avoid modifying the original array
    print("After sorting:", sorted_array)
   
    # Test data 2: contains duplicate elements
    test_array2 = [5, 2, 9, 5, 2, 3, 5]
    print("\nBefore sorting:", test_array2)
    print("After sorting:", shell_sort(test_array2.copy()))
   
    # Test data 3: reversed array
    test_array3 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    print("\nBefore sorting:", test_array3)
    print("After sorting:", shell_sort(test_array3.copy()))

Code analysis:

  1. def shell_sort(arr):Define the Shell sort function.
  2. n = len(arr)Get the array length.
  3. gap = n // 2Initialize the increment. This is the most classic starting point for the increment sequence in Shell sort.
  4. while gap > 0:Outer loop, controlling the increment to gradually decrease until it becomes 0 (after actually being 1 and finishing execution,gap //= 2it becomes 0 and exits).
  5. for i in range(gap, n):Inner loop. Starting from the indexgapStart traversing.ipoints to the current element to be inserted. Note that this loop cleverly handles all elements withgapsubsequences with ... as the interval.
  6. temp = arr[i]andj = i: save the value of the current element, and usejto record the position where it should be inserted in the current subsequence.
  7. while j >= gap and arr[j - gap] > temp:This is the core of insertion sort. Within the same subsequence (byj - gapindexing to access the previous element), if the previous element is larger thantempif it is larger, move the previous element backwardgapposition.
  8. arr[j] = temp: the savedtempinsert the value into the correct position.
  9. gap //= 2After one round of sorting, halve the increment and perform the next round of finer sorting.
  10. return arr: return the sorted array.

Selection of the increment sequence.

The choice of increment sequence directly affects the performance of Shell sort. Above we used Shell's original sequence (n/2, n/4, ..., 1), but it is not optimal. Below are several common increment sequences:

Sequence name Generation formula Characteristics and complexity.
Shell original sequence $gap = \lfloor \frac{n}{2} \rfloor, gap = \lfloor \frac{gap}{2} \rfloor...$ Simple to implement, with a worst-case time complexity of $O(n^2)$.
Hibbard sequence $1, 3, 7, 15, ..., 2^k - 1$ The worst-case time complexity can be improved to $O(n^{3/2})$.
Knuth sequence $1, 4, 13, 40, ..., (3^k - 1) / 2$ (less than n) The average time complexity is about $O(n^{1.25})$, and it is commonly used in practice.
Sedgewick sequence $1, 5, 19, 41, 109, ...$ (a mix of $9 \times 4^k - 9 \times 2^k + 1$ and $4^k - 3 \times 2^k + 1$) It is one of the best known sequences, with a worst-case complexity reaching $O(n^{4/3})$.

Example implementation using Knuth's sequence

Example

def shell_sort_knuth(arr):
    n = len(arr)
    # Generate Knuth increment sequence: 1, 4, 13, 40, 121, ...
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1  # Generate the maximum initial increment
   
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3  # Knuth suggests dividing by 3 each time
    return arr

# Test the Knuth sequence version
test_array = [33, 12, 56, 78, 2, 45, 67, 89, 1, 23]
print(Before sorting with the Knuth sequence:, test_array)
print(After sorting with the Knuth sequence:, shell_sort_knuth(test_array.copy()))

Algorithm characteristics and complexity analysis

Time complexity

The time complexity analysis of Shell sort is very complex because it depends on the chosen increment sequence.

  • Worst caseWhen using Shell's original sequence, the worst-case time complexity is $O(n^2)$.
  • Average case: For better increment sequences (such as Knuth, Sedgewick), the average time complexity is between $O(n^{1.25})$ and $O(n^{1.5})$.
  • Best caseWhen the array is already sorted, the complexity can approach $O(n \log n)$.

Space complexity

  • Shell sort isIn-place sortingalgorithm, requiring only a constant amount of extra space (such astemp, gap, i, jvariables), so the space complexity is $O(1)$.

Stability

  • Shell sort isunstablesorting algorithm. Because when sorting in groups by increment, equal elements may be placed into different subsequences and their relative order may be changed due to movement.

Simple comparison with other sorting algorithms

Features Shell Sort Insertion Sort Merge Sort Quicksort
Average time complexity. $O(n^{1.25})$ ~ $O(n^{1.5})$ $O(n^2)$ $O(n \log n)$ $O(n \log n)$
Space complexity $O(1)$ $O(1)$ $O(n)$ $O(\log n)$
Stability unstable Stable Stable unstable
Advantages Good performance for medium-sized data, in-place sorting Simple, efficient for small data or nearly sorted data Stable, excellent time complexity Fastest in average cases.
Disadvantages Complexity analysis is difficult, and the choice of increment sequence has a great impact. Low efficiency with large data volumes. Requires extra space. In the worst case, it degrades to $O(n^2)$.

More code examples.

other extensions