private static void quickSort(int[] arr) {
     quickSort(arr, 0, arr.length - 1);
 }

 private static void quickSort(int[] arr, int l, int r) {
     if (l == r) return;

     int pivot = arr[l + r >>> 1], i = l - 1, j = r + 1;
     while (i < j) {
         while (arr[++i] < pivot);
         while (arr[--j] > pivot);
         if (i < j) swap(arr, i, j);
     }

     quickSort(arr, l, j);
     quickSort(arr, j + 1, r);
 }

private static void mergeSort(int[] arr) {
      mergeSort(arr, 0, arr.length - 1);
  }

  private static void mergeSort(int[] arr, int l, int r) {
      if (l == r) return;

      int m = l + r >>> 1;
      mergeSort(arr, l, m);
      mergeSort(arr, m + 1, r);

      merge(arr, l, m, r);
  }

  private static void merge(int[] arr, int l, int m, int r) {
      int p = l, q = m + 1;
      int[] tmp = new int[r - l + 1];
      int i = 0;
      while (p <= m && q <= r) tmp[i++] = arr[p] <= arr[q] ? arr[p++] : arr[q++];
      while (p <= m) tmp[i++] = arr[p++];
      while (q <= r) tmp[i++] = arr[q++];

      for (int val : tmp) arr[l++] = val;
  }

public class HeapSort {
  public static void main(String[] args) {

  }

  private static int[] arr;
  private static int size;

  public static void sort(int[] arr) {
    arr = nums;
    size = arr.length;

    /**init heap*/
    for (int i = size / 2; i >= 0; i--) {
       down(i);
    }

    /**swap*/
    while (size > 0) {
        swap(arr, 0, --size);
        down(0);
    }
  }

  private static void down(int index) {
    int tmp = index;
    if (index * 2 + 1 < size && arr[index] < arr[index * 2 + 1]) tmp = index * 2 + 1;
    if (index * 2 + 2 < size && arr[tmp] < arr[index * 2 + 2]) tmp = index * 2 + 2;

    if (tmp != index) {
        swap(arr, index, tmp);
        down(tmp);
    }
  }

  private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }
}