Shell Sort - Java Implementation

Sorting Algorithm Tutorials - Herong's Tutorial Examples

∟Shell Sort Algorithm and Java Implementation

∟Shell Sort - Java Implementation

This section provides a tutorial on how to implement the Shell Sort algorithm in Java.

Here is my Java implementation of Shell Sort algorithm:

/* HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.sort().
 * All sorting methods should have a signature of
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 2008 HerongYang.com. All Rights Reserved.
 */
public class HyArrays {
  public static void shellSort(HyObject[] a, int fromIndex,
     int toIndex) {
     int h = 1;
     while (h<toIndex-fromIndex) h = 3*h + 1;
     while (h>1) {
        h = h/3;
        for (int i=fromIndex+h; i<toIndex; i++) {
           HyObject d = a[fromIndex+i];
           int j = i;
           while (j>=fromIndex+h && d.compareTo(a[fromIndex+j-h])<0) {
              a[fromIndex+j] = a[fromIndex+j-h];
              j = j - h;
           }
           a[fromIndex+j] = d;
        }
     }
  }
}

Note that:

If you replace h by 1, the code should identical to the insertion sort.

In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old implementation:

/* HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.
 * All sorting methods should have a signature of
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 2011 HerongYang.com. All Rights Reserved.
 */
   public static void shellSort(Object[] a, int fromIndex,
      int toIndex) {
      int h = 1;
      while (h<toIndex-fromIndex) h = 3*h + 1;
      while (h>1) {
         h = h/3;
         for (int i=fromIndex+h; i<toIndex; i++) {
            Comparable d = (Comparable)a[fromIndex+i];
            int j = i;
            while (j>=fromIndex+h && d.compareTo(a[fromIndex+j-h])<0) {
               a[fromIndex+j] = a[fromIndex+j-h];
               j = j - h;
            }
            a[fromIndex+j] = d;
         }
      }
   }