void quickSort(int arr[], int left, int right) {	//Confirmed
		int index = partition(arr, left, right);
		if (left < index - 1) { 	//when sorting  2 3 1, will return 2 1 3, left point at 3 and 2 1 unsorted			
			quickSort(arr, left, index - 1);		
		}
		if (index < right) {		//when sorting 3 1 2, will return 1 3 2, index at 3 and right is 2. 
			quickSort(arr, index, right);
		}
	}
	
	int partition(int arr[], int left, int right) {
		int pivot = arr[(left + right) / 2];
		while (left < right) { //1. left -> 2, right -> 3  2. left -> 2, right -> 2. Be clear with these two cases, and know how do decide comparison in quickSort();  
			while (arr[left] < pivot)
				left++;						//cannot write while (arr[left++] < pivot);
			while (arr[right] > pivot)
				right--;
			if (left < right) {
				swap(arr, left++, right--);
			}
		}
		return left;		//when return, we want left to point at a number > pivot. and all orgin_left : left - 1 <= pivot.
	}
	
	void swap(int arr[], int left, int right) {
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
	}