ShellSortについて、Javaでサンプルプログラムを書いてみました。
ShellSort.java

import java.util.Scanner;
public class ShellSort {
    static int debug = 0;
    public static void main(String[] args) {
	if (args.length > 0 ){
	    if(args[0].equals("-d")) debug = 1;
	    else if (args[0].equals("-d2")) debug = 2;
	}
	Scanner sc = new Scanner(System.in);
	System.out.print("データの個数を入力して下さい  ");
	int n = sc.nextInt();
	int[] a = new int[n];
	for (int i=0; i<n; i++) a[i] = sc.nextInt();
	sort(a);
	System.out.println(toString(a));
    }
    public static void sort(int[] a) {
	int h;
	for(h=1; h<a.length/9; h=h*3+1);
	for(; h>0; h/=3) {
	    for(int i=h;i<a.length;i++){
		for(int j=i;j>=h&&a[j-h]>a[j];j-=h){
		    int tmp = a[j];
		    a[j] = a[j-h];
		    a[j-h] = tmp;
		    if(debug > 1)
			System.out.println("h="+h+"i="+i+",j="+j+": "+toString(a));
		}
		if(debug>0)
		    System.out.println("h="+h+"i="+i+": "+toString(a));
	    }    
	}
    }
    public static String toString(int[] a) {
	StringBuffer sb = new StringBuffer();
	for (int i=0; i<a.length; i++)
	    sb.append(a[i] + " ");
	return sb.toString();
    }
}