public int[] sort(int[] input) {
        arr = new int[input.length + 1];
        for (int i = 0; i < input.length; ++i) {
            arr[i + 1] = input[i];
        }
        heapify(arr, arr.length - 1);
        return maxDeletion(arr, input);
    }