// сортировка Шелла с предустановленными значениями длин промежутков самая быстрая при паре тысяч полигонов, а нам она нужны только при отрисовке малого количества полигонов

import java.util.Vector;
public class Ksort {
    private static final int[] d = {1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901, 84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774, 58548857, 157840433, 410151271, 1131376761, 2147483647};

public static void sort(Vector e) {
        Face temp=null;
        int i=0, j=0, k=0, m = 0,s=e.size();
        
        while(d[m] < s) ++m;
        
        while(--m >= 0) {
            k = d[m];
            for(i=k; i<s; i++) { // k-сортировка
                j = i;
                temp = (Face)e.elementAt(i);
int tmpsz=temp.getS();
                while( (j >= k) && (((Face)e.elementAt(j-k)).getS() > tmpsz) ) {
                    e.setElementAt(e.elementAt(j - k),j);
                    j -= k;
                }
                e.setElementAt(temp,j);
            }
        }
    }

public static void sort(Face[] e) {
        Face temp=null;
        int i=0, j=0, k=0, m = 0,s=e.length,tmpsz;
        
        while(d[m] < s) ++m;
        
        while(--m >= 0) {
            k = d[m];
            for(i=k; i<s; i++) { // k-сортировка
                j = i;
                temp = e[i];
                if(temp==null)temp=new Triangle(new Vertex(),new Vertex(),new Vertex(),0);
                tmpsz=temp.getS();
                while( (j >= k) && ((e[j-k]).getS() > tmpsz) ) {
                    e[j]=e[j - k];
                    j -= k;
                }
                e[j]=temp;
            }
        }
    }

}