Algorithm - Heap Sort

Heap Sort
Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it 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.

It's an In-Place algorithm, but It's not a stable sort.

Solution

public class HeapSort {
    private static int num;
    public static void sort(int array[]) {
        doSort(array);
        for (int i = num; i > 0; i--) {
            swap(array, 0, i);
            num = num - 1;
            maxHeap(array, 0);
        }
    }
    public static void doSort(int arr[]) {
        num = arr.length - 1;
        for (int i = num / 2; i >= 0; i--) {
            maxHeap(arr, i);
        }
    }
    public static void maxHeap(int array[], int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int max = i;
        if (left <= num && array[left] > array[i]) {
            max = left;
        }
        if (right <= num && array[right] > array[max]) {
            max = right;
        }

        if (max != i) {
            swap(array, i, max);
            maxHeap(array, max);
        }
    }
    public static void swap(int array[], int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int array[] = {11, 8, 34, 5, -4, 19, 0, 25, 97, 83, 20};
        sort(array);
        for (int i = 0; i < array.length; i++) {
            if (i > 0) {
                System.out.print(", ");
            }
            System.out.print(array[i]);
        }
    }
}

Result:
-4, 0, 5, 8, 11, 19, 20, 25, 34, 83, 97

Finally, Which sort is best?
Quick Sort is generally considered to be the best sorting algorithm. Compare from other sorting techniques, quick sort is much better than others.

Reason
Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.

To Know more sorting algorithms, just visit WIKIPEDIA