普通のヒープソートなり.

heap_sort.c

#include <stdio.h>
#include <stdlib.h>

void print_array(int * array, int size) {
    int i = 0;
    printf("{ ");
    while (1) {
        printf("%d", array[i]);
        if (++i >= size) {
            printf("}\n");
            break;
        } else {
            printf(",");
        }
    }
}

void swap(int *i, int *j) {
    int temp;
    temp = *i;  *i = *j;  *j = temp;
}

void down_heap(int *array, int left, int right) {
    int child;
    int parent = left;
    int temp = array[left];
    int cl, cr;
    while(parent < (right + 1) / 2){
        cl = parent * 2 + 1;
        cr = cl + 1;
        if((cr <= right) && (array[cr] > array[cl])){
            child = cr;
        }else{
            child = cl;
        }
        if(temp >= array[child]) break;
        array[parent] = array[child];
        parent = child;
    }
    array[parent] = temp;
}

void heap_sort(int *array, int size) {
    int i;
    for(i = (size - 1) / 2; i >= 0; i--){
        down_heap(array, i, size - 1);
    }
    for (i = size - 1; i > 0; i--) {
        swap(&array[0], &array[i]);
        down_heap(array, 0, i - 1);
    }
}

int main(void) {
    int i, tests[4][5] = {
        { 1, 2, 3, 4, 5 },
        { 2, 3, 4, 5, 1 },
        { 4, 5, 3, 2, 3 },
        { 5, 4, 3, 1, 1 }
    };
    for (i = 0; i < 4; i++) {
        heap_sort(tests[i], 5);
        print_array(tests[i], 5);
    }
    return 0;
}