package sort;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ShareSort {

  rivate static class ShearColList<E> extends AbstractList<E> {

    private final List<E> SRC;
    private final int COL;
    private final int SHEAR;

    public ShearColList(List<E> src, int shear, int col) {
      this.SRC = src;
      this.COL = col;
      this.SHEAR = shear;
    }

    private int srcIndex(int index) {
      int off = isEven(index) ? COL : SHEAR - COL - 1;
      return index * SHEAR + off; 
    }

    @Override
    public E get(int index) {
      return SRC.get(srcIndex(index));
    }

    public E set(int index, E element) {
      return SRC.set(srcIndex(index), element);
    };

    @Override
    public int size() {
      boolean ext = srcIndex(SRC.size() / SHEAR) < SRC.size(); 
      return (SRC.size() / SHEAR) + (ext ? 1 : 0);
    }

  }

  private static boolean isEven(int n) {
    return (n % 2) == 0;
  }

  public static<E extends Comparable<E>> List<E> sort(List<E> list) {
    int shear = (int) Math.sqrt(list.size());
    int log2 = 1;
    for (int a = shear; a != 0; a /= 2, log2++) ;
    for (int i = 0; i < log2; i++) {
      for (int off = 0; off < list.size(); off += shear) {
        Collections.sort(list.subList(off, Math.min(off + shear, list.size())));
      }
      for (int j = 0; j < shear; j++) {
        Collections.sort(new ShearColList<E>(list, shear, j));
      }
    }
    return list;
  }
	
  public static void main(String ...args) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < 10; i++) {
      list.add(i);
    }
    Collections.shuffle(list);
    System.out.println(list);
    System.out.println(sort(list));
  }
}