import java.util.*;

public class ShellSort {
    public int[] shellSort(int[] A, int n) {
        for(int step = n /2; step > 0; step = step / 2) {
            for(int i = step; i < n; i = i + step) {
                int temp = A[i];
                
                int j = i;
                while( j - step >= 0 &&temp < A[j -step]){
                    A[j] = A[j - step];
                    j = j - step;
               }
               A[j] = temp;
             }
            
    
          }
          return A;
    }
}