Shell Sort

I. Concept and Introduction

Shell Sort is a variation of insertion sort, designed to improve upon the direct insertion sort algorithm.

Also known as Diminishing Increment Sort, it was named after DL. Shell, who proposed it in 1959.

It works by comparing elements that are a certain distance apart, with the distance decreasing as the algorithm progresses, until the final pass compares adjacent elements.

II. Applicability

The time complexity of Shell Sort is O(n^(1.3-2)), and the space complexity is constant, O(1). Although it is not as fast as quick sort algorithms with a time complexity of O(n(logn)), it performs well for medium-sized data sets. However, it is not the best choice for very large data sets. Overall, it is significantly faster than algorithms with a complexity of O(n^2).

III. Process Illustration

Shell Sort aims to speed up the process by modifying insertion sort. It swaps non-adjacent elements to partially sort the array, and finally uses insertion sort to sort the partially ordered array.

Here, we choose the initial increment gap=length/2, and reduce it using gap = gap/2, represented by the sequence {n/2,(n/2)/2...1}.

Illustrative example:

(1) First pass with initial increment gap = length/2 = 4

(2) Second pass, increment reduced to 2

(3) Third pass, increment reduced to 1, resulting in the final sorted array

IV. Java Example Code

Source Code Download: Download

The innermost loop is essentially an 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(' ');
        }
    }
}