void shellSort (int *array, int len, int *seq, int seqLen){
    int i;
    for (i = seqLen - 1; seq[i] > len / 2 && i > 0; i--);

    while (i >= 0){
        int n = seq[i];
        for (int j = n; j < len; j++){
            int t = array[j];
            int k;
            for (k = j; k >= n && t < array[k - n]; k -= n){
                array[k] = array[k - n];
            }
            array[k] = t;
        }
        i--;
    }
}

void sink (int *array, int len, int i){
    while (i < len){
        int root = i;
        int lChild = i * 2 + 1;
        int rChild = i * 2 + 2;

        if (lChild < len && array[lChild] > array[root]){
            root = lChild;
        }

        if (rChild < len && array[rChild] > array[root]){
            root = rChild;
        }

        if (root == i){
            return;
        }

        int t = array[root];
        array[root] = array[i];
        array[i] = t;

        i = root;
    }
}

void buildHeap (int *array, int len){
    int index = len / 2;

    for (; index--;){
        sink(array, len, index);
    }
}

void heapSort (int *array, int len){
    buildHeap(array, len);

    for(; len--;){
        int t = array[0];
        array[0] = array[len];
        array[len] = t;
        sink(array, len, 0);
    }
}

int main (int argc, char **argv){
    int d[] = {1, 4, 10, 23, 57, 132, 301, 701, 1750};
    int arr[] = {1, 3, 5, 7, 9, 0, 8, 6, 4, 2};
//  shellSort(arr, 10, d, 9);
    heapSort(arr, 10);
    for (int i = 0; i < 10; i++){
        printf("%d%s", arr[i], i == 9 ? "\n" : " ");
    }
}