Heap Sort

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.(Wikipedia)

Worst case performance - O(n log n)

Heap sort

C++

void heap_sort(int array[],int heap_size){
    build_max_heap(array,heap_size);
    for (int i = heap_size; i > 0; i--) {
        swap(array,0, i);
        heap_size = heap_size - 1;
        max_heapify(array, 0,heap_size);
    }
}

void build_max_heap(int array[], int heap_size){
    for (int i = heap_size / 2; i >= 0; i--){
        max_heapify(array, i,heap_size);
    }
}

void max_heapify(int array[], int i,int heap_size){
    int l = left(i);
    int r = right(i);
    int largest;
    if (l <= heap_size && array[l] > array[i]){
        largest = l;
    }
    else{
        largest = i;
    }
    if (r <= heap_size && array[r] > array[largest]){
        largest = r;
    }
    if (largest != i){
        swap(array,i, largest);
        max_heapify(array, largest,heap_size);
    }
}

int left(int i){
    return 2 * i;
}

int right(int i){
    return 2 * i + 1;
}

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

Java

    public void heap_sort(int[] array) {
        build_max_heap(array);
        for (int i = heap_size; i > 0; i--) {
            swap(0, i);
            heap_size = heap_size - 1;
            max_heapify(array, 0);
        }
    }
   
    public void build_max_heap(int[] array) {
        heap_size = array.length - 1;
        for (int i = heap_size / 2; i >= 0; i--) {
            max_heapify(array, i);
        }
    }
   
    public void max_heapify(int[] array, int i) {
        int l = left(i);
        int r = right(i);
        int largest;
        if (l <= heap_size && array[l] > array[i]) {
            largest = l;
        } else {
            largest = i;
        }
        if (r <= heap_size && array[r] > array[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(i, largest);
            max_heapify(array, largest);
        }
    }
   
    public int left(int i) {
        return 2 * i;
    }
   
    public int right(int i) {
        return 2 * i + 1;
    }
   
    public void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

Matlab

function array = heap_sort(array)
    heap_size = numel(array);
    array = build_max_heap(array,heap_size);
    for i = numel(array):-1:2
        array([i 1]) = array([1 i]);
        heap_size = heap_size - 1;
        array = max_heapify(array,heap_size,1);
    end
end

function array = build_max_heap(array,heap_size)
    for i = floor(heap_size/2):-1:1
        array = max_heapify(array,heap_size,i);
    end
end

function array = max_heapify(array,heap_size,i)
    l = left(i);
    r = right(i);
    if l <= heap_size && array(l) > array(i)
        largest = l;
    else
        largest = i;
    end
    if r <= heap_size && array(r) > array(largest)
        largest = r;
    end
    if largest ~= i
        array([largest i]) = array([i largest]);
        array = max_heapify(array,heap_size,largest);
    end
end

function l = left(i)
    l = 2 * i;
end

function r = right(i)
    r = 2 * i + 1;
end

Python

import math

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def max_heapify(array,heap_size,i):
    l = left(i)
    r = right(i)
    if l <= heap_size and array[l] > array[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size and array[r] > array[largest]:
        largest = r
    if largest != i:
        array[largest],array[i] = array[i],array[largest]
        max_heapify(array,heap_size,largest)

def build_max_heap(array,heap_size):
    for i in range(math.floor(heap_size/2),-1,-1):
        max_heapify(array,heap_size,i)

def heap_sort(array):
    heap_size = len(array)- 1
    build_max_heap(array,heap_size)
    for i in range(heap_size,0,-1):
        array[i],array[0] = array[0],array[i]
        heap_size = heap_size - 1
        max_heapify(array,heap_size,0)