#include <iostream>
using namespace std;

template <typename T>
void sink(T arr[], int pos, int N, int d) {
    int start(pos*d + 1), max_index(start);
    while(start < N) {
        // Find the max amongst direct "children" of position `pos`
        for(int i = start + 1; (i < start + d) && (i < N); i++) {
            if (arr[i] > arr[max_index]) {
                max_index = i;
            }
        }
        // If arr[pos] is less than the max we found, switch them and proceed
        if (arr[pos] < arr[max_index]) {
            // Switch arr[pos] and arr[max_index] to enforce heap condition
            T tmp = arr[pos];
            arr[pos] = arr[max_index];
            arr[max_index] = tmp;
            // Update pos and start to sink "recursively"
            pos = max_index;
            start = pos*d + 1;
            max_index = start;
        } else { // Else, there is nothing to worry about further ...
            break;
        }
    }
}

template <typename T>
void dheapsort(T arr[], int N, int d) {
    // The for loop "heapify" the array.
    for (int k = N/d; k >= 0; k--) {
        sink<T>(arr, k, N, d);
    }
    // We exchange the max (located at arr[0] since the array became a heap)
    // with the last element.
    // Then we enforce the heap condition on the N-1 remaining elements.
    // N is then decreased
    // (...) so on.
    while (N > 1) {
        T tmp = arr[N-1];
        arr[N-1] = arr[0];
        arr[0] = tmp;
        sink<T>(arr, 0, --N, d);
    }
}

// Then you just have to use it with the parameters you want ...
// An example :

int main() {
    int test[10] = {1, 3, 2, 5, 6, 8, 2, 8, 10, 11};
    dheapsort(test, 10, 3);
    for (int i = 0; i < 10; i++)
        cout << "test[" << i << "] : " << test[i] << endl;
    return 0;
}