import java.util.Scanner;

public class ShellSort {

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

System.out.print("Enter the number of elements : ");

int n = sc.nextInt();

int arr[] = new int[n];

System.out.println("Enter " + n + " elements :");

for (int i = 0; i < n; i++)

arr[i] = sc.nextInt();

shellSort(arr);

System.out.println("\nThe sorted array : ;");

for (int i = 0; i < n; i++)

System.out.print(arr[i] + " ");

System.out.println();

}

static void shellSort(int[] nums) {

int h = 1;

int n = nums.length;

while(h < n) {

h = h * 3 + 1;

}

h = h / 3;

int c, j;

while (h > 0) {

for (int i = h; i < n; i++) {

c = nums[i];

j = i;

while (j >= h && nums[j - h] > c) {

nums[j] = nums[j - h];

j = j - h;

}

nums[j] = c;

}

h = h / 2;

}

}

}