Heap Sort

void swap(int arr[], int i, int j)
{
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}

void heapify(int arr[], int length, int i)
{
    int left = 2*i + 1;
    int right= 2*i + 2;
    int largest;
    if (left < length && arr[left] > arr[i])
    {
        largest = left;
    }
    else
    {
        largest = i;
    }
    if (right < length && arr[right] > arr[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
        swap(arr, i, largest);
        heapify(arr, length, largest);
    }
}

void buildHeap(int arr[], int length)
{
    int i;
    for (i = length/2; i >= 0; i--)
    {
        heapify(arr, length, i);
    }
}

void heapSort(int arr[], int length)
{
    buildHeap(arr, length);
    int i;
    for (i = length - 1; i > 0; i = i - 1)
    {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}