Shell Sort Comparable Array Items in Java

Shell sort is considered as an extension of insertion sort algorithm.

Insertion sort algorithm is not suggested for large input sets but shell sort comes with increased speed achievements for insertion sort algorithm.

Shell sort achieves speed improvement by exchanging of input entries that are away from each other and produces partially sorted input data sets.

Space and time complexity values are :

Worst case performance : О(n²)
Best case performance : О(n log² n)
Average case performance : depends on gap sequence

Space complexiy :  О(n) total, O(1) auxiliary

There is an animation for the shell sort algorithm at :

Following is the Java implementation of the Shell Sort algorithm where the sort method accepts an array of Comparable items as input parameter.

package basics;

public class ShellSort {

 public static void sort(Comparable[] a) {

  // Sort a[] into increasing order.
  int N = a.length;
  int h = 1;
  while (h < N / 3)
   h = 3 * h + 1;
  
  // h-sort the array.
  while (h >= 1) { 
   for (int i = h; i < N; i++) { 
    for (int j = i; j >= h && (a[j].compareTo(a[j - h]) < 0); j -= h) {
     Comparable temp = a[j];
     a[j] = a[j - h];
     a[j - h] = temp;
    }
   }
   h = h / 3;
  }

 }

 public static void main(String[] args) {

  String[] strArr = { "S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E" };

  System.out.println("Before Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println("\n");

  sort(strArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < strArr.length; i++)
   System.out.print(strArr[i] + " ");
  System.out.println();

  Integer[] intArr = { 9, 8, 7, 6, 6, 5, 4, 3, 2, 2, 1 };

  System.out.println();
  System.out.println("Before Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println("\n");

  sort(intArr);

  System.out.println("After Sort = ");
  for (int i = 0; i < intArr.length; i++)
   System.out.print(intArr[i] + " ");
  System.out.println();
 }
}

Create a ShellSort.java file in your workspace.

When the main method inside the ShellSort class executed it is going to print :

Before Sort =
S O R T E X A M P L E

After Sort =
A E E L M O P R S T X

Before Sort =
9 8 7 6 6 5 4 3 2 2 1

After Sort =
1 2 2 3 4 5 6 6 7 8 9


Because sort method accepts an array or Comparable items, so it is safe to send an array of items where each item implements Comparable interface in Java.

Integer and String classes in Java implement Comparable interface so it is acceptable to send this types as parameters to sort method.