public class SortDemo() {
	public static void bubbleSort(int[] arr) {
		int n = arr.length;
		boolean flag;
		for (int i = 0; i < n; i++) {
			flag = true;
			for (int j = 0; j < n - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					flag = false;
					arr[j] ^= arr[j + 1];
					arr[j + 1] ^= arr[j];
					arr[j] ^= arr[j + 1];
				}
			}
			if (flag) {
				break;
			}
		}
	}
	public static void quickSort(int[] arr, int l, int r){
		if (l >= r) return;
		int tar = arr[l];
		int i = l;
		int j = r;
		while (i < j) {
			while (arr[j] >= tar && i < j) j--;
			if (i < j) arr[i++] = arr[j];
			while (arr[i] <= tar && i < j) i++;
			if (i < j) arr[j--] = arr[i];
		}
		arr[i] = tar;
		quickSort(arr, l, i - 1);
		quickSort(arr, i + 1, r);
	}
	public static void insertSort(int[] arr) {
		int n = arr.length;
		for (int i = 1; i < n; i++) {
			int temp = arr[i];
			int j = i - 1;
			while (j >= 0 && arr[j] > temp) {
				arr[j + 1] = arr[j];
				j--;
			}
			arr[j + 1] = temp;
		}
	}


	public static void shellSort(int[] arr) {
		int n = arr.length;
		for (int step = n / 2; step > 0; step /= 2) {
			for (int i = step; i < n; i++) {
				int j = i - step;
				int target = arr[i];
				while (j >=0 && arr[j] > target) {
					arr[j + step] = arr[j];
					j -= step;
				}
				arr[j + step] = target;
			}
		}
	}
	public static void selectionSort(int[] arr) {
		int n = arr.length;
		for (int i = 0; i < n - 1; i++) {
			int min = i;
			for (int j = i + 1; j < n - i; j++) {
				if (arr[j] < arr[min]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}


	public static void heapify(int[] arr, int n, int i) {
		int max = i;
		int lSon = i * 2 + 1;
		int rSon = i * 2 + 2;
		if (lSon < n && arr[lSon] > arr[max]) max= lSon;
		if (rSon < n && arr[rSon] > arr[max]) max= rSon;
		if (max != i) {
			int temp = arr[max];
			arr[max] = arr[i];
			arr[i] = temp;
		}
		heapify(arr, n, max);
	}

	public static void heapSort(int[] arr) {
		int n = arr.length;
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i);
		}
		for (int i = n - 1; i > 0; i--) {
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			heapify(arr,i, 0);
		}
	}

	public static void mergeSort(int[] arr, int l, int r) {
		if (l >= r) return;
		int mid = (r - l) / 2 + l;
		mergeSort(arr, l, mid);
		mergeSort(arr, mid + 1, r);

		int[] temp = new int[r - l + 1];
		int i = l;
		int j = mid + 1;
		int k = 0;
		while (i <= mid && j <= r) {
			if (arr[i] <= arr[j]) temp[k++] = arr[i++];
			else temp[k++] = arr[j++];
		}
		while (i <= mid) temp[k++] = arr[i++];
		while (j <= r) temp[k++] = arr[j++];
		for (i = 0; i < k; i++) {
			arr[l + i] = temp[i];
		}
	}
}