public void headAdjust(int[] arr, int s, int m) {

    int tmp = arr[s];

    for (int i = 2 * s + 1; i < m; i = 2 * i + 1) {
        if (i != m - 1 && arr[i + 1] > arr[i])
            ++i;

        if (tmp < arr[i]) {
            arr[s] = arr[i];
            s = i;
        }

        else
            break;
    }


    arr[s] = tmp;
}



public void headSort(int[] arr) {
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        headAdjust(arr, i, arr.length);
    }


    for (int i = arr.length - 1; i > 0; i--) {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;

        headAdjust(arr, 0, i);
    }
}

private void mergeSort(int[] data, int[] temp, int left, int right) {

    if (left < right) {
        int middle = (left + right) / 2;
        mergeSort(data, temp, left, middle);
        mergeSort(data, temp, middle + 1, right);

        merge(data, temp, left, middle, right);
    }
}



private void merge(int[] data, int[] temp, int left, int middle, int right) {

    int i = left, j = middle + 1, k = 0;

    while (i <= middle && j<= right) {
        if (data[i] <= data[j])
            temp[k++] = data[i++];

        else
            temp[k++] = data[j++];

    }


    while (i <= middle)
        temp[k++] = data[i++];

    while (j <= middle)
        temp[k++] = data[j++];

    for (i = 0; i < k; i++) {
        data[left + i] = temp[i];
    }
}