static void SelectionSort(int[] A) { // Ex 1a Complete the method SelectionSort
		for (int i = 0; i < A.length - 1; i++) {
			int minIndex = i; // Index of smallest remaining value.
			minIndex = findIndexSmallest(A, i, A.length-1);
			swap(A, minIndex, i);
		}
	}

static void InsertionSort(int[] inputArray) { // Ex 1b Complete the method InsertionSort
		for (int i = 1; i < inputArray.length; i++) { //อย่าลืมว่าเริ่มจาก index 1 เพราะเรา Assume ว่าตัวแรกน้อยสุดอยู่ละ ไม่ต้องไปสนใจ
			int tempValue = inputArray[i]; //เอาค่าออกมา temporary เพ่ือมา Compare นู้นนี่
			for (int j = i-1; j >= 0 && inputArray[j] > tempValue; j--) { //for loop นี้เอาไว้เช็คข้างหน้าที่เรียงแล้วให้สลับ 
				//condition คือ reach beginning & เจอตัวเลขน้อยกว่า ; ทำไปเรื่อย j--
				swap(inputArray, j+1, j); //ขยับ j+1 ไป j
				printArray(inputArray);	//Print เพื่อดูทุกขั้นตอน
			}
		}
	}

private static void RecursiveMergeSort(int[] inputArray) {
		int inputLength = inputArray.length; //8
		
		if (inputLength < 2) { //ตรงนี้เปรียบเสมือน Base case ใน recursive - ถ้าเป็น one element array แล้ว
			// หรือไม่ก็เป็น empty array ก็ให้หยุด -> return
			return;
		}
 
		int midIndex = inputLength / 2; //4 -- ถึงถ้าเป็น decimal value มันก็จะปัดลงหมดเพราะเราเรียก int
		int[] leftHalf = new int[midIndex]; //Initialise Array with length of 4 - Half the length of original array
		int[] rightHalf = new int[inputLength - midIndex]; // Initialise Array with length of 8-4 = 4
		// จริง ๆ rightHalf จะใช้เป็น midIndex เหมือนกันก็ได้ แต่ว่ามันจะไม่ work ถ้า original array เป็นเลขคี่
 
		// leftHalf array
		for (int i = 0; i < midIndex; i++) { // Loop from 0 to length of leftHalf (index 0-3) ก็ได้ 4 elements
			//Put first half member to array to be leftHalf
			leftHalf[i] = inputArray[i]; //leftHalf array will contain all the elements of the left half of original array
		}
		
		// rightHalf array
		for (int i = midIndex; i < inputLength; i++) { //The other way round (index 4-7) ได้ 4 elements
			rightHalf[i - midIndex] = A[i]; //เริ่มจาก Index 4-4=0 ของ rightHalf เพื่อเก็บได้อย่างถูกต้อง
		}
		
		RecursiveMergeSort(leftHalf); //Run all the way to base case X | X | X | X  -- X | X | X | X
		RecursiveMergeSort(rightHalf);
		
		//ตอนนี้คือได้เป็น one element array กันหมดแล้ว
		
		merge(inputArray, leftHalf, rightHalf);
 
	}
 
	/**
	 * Merges two sorted integer arrays into one sorted array.
	 *
	 * This method merges two sorted integer arrays, `leftHalf` and `rightHalf`,
	 * into a single sorted array `A`. It iterates through both input arrays,
	 * comparing elements and placing them in ascending order in the resulting
	 * merged array.
	 *
	 * @param A         The target integer array where the sorted elements will be
	 *                  stored.
	 * @param leftHalf  The first sorted integer array to be merged.
	 * @param rightHalf The second sorted integer array to be merged.
	 */
	private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf) {
		int leftSize = leftHalf.length;
		int rightSize = rightHalf.length;
		int i = 0; //Walk from left half array
		int j = 0; //Walk from right half array
		int k = 0; //Walk through merged array
 
		while (i < leftSize && j < rightSize) { //ทำไปจนกว่าจะ run out of element in left or right array
			if (leftHalf[i] < rightHalf[j]) {
				inputArray[k] = leftHalf[i];
				i++;
				k++;
			} else {
				inputArray[k] = rightHalf[j];
				j++;
				k++;
			}
		}
		// Copy any remaining elements from the leftHalf array, if any.
		while (i < leftSize) { //ถ้าแบบยังเหลือ 1 ตัว แต่ถ้าไม่เหลือแล้วก็ skip part นี้ไปเลย
			inputArray[k] = leftHalf[i];
			i++;
			k++;
		}
		// Copy any remaining elements from the leftHalf array, if any.
		while (j < rightSize) {
			inputArray[k] = rightHalf[j];
			j++;
			k++;
		}
	}

static void RecursiveQuickSort(int[] inputArray, int lowIndex, int highIndex) { //index 0 to last element of an array
		if (lowIndex >= highIndex) {
			return;
		}
			int pivot = inputArray[highIndex]; //เลือก Pivot อยู่ท้ายสุดของ Array
			
			//Partitioning จะต้องมี Left Pointer, Right Pointer 
			//โดย Left Pointer จะ walk ไปเรื่อย ๆ จนกว่าจะเจอเลขที่ bigger than the pivot แล้วหยุด
			//โดย Right Pointer จะได้จากขวามาซ้ายไปเรื่อย ๆ จนกว่าจะเจอเลขที่ smaller than the pivot แล้วหยุด
			//แล้วก็ Swap เลขที่ตำแหน่ง lp, rp อยู่ แล้วก็ repeat ไปเรื่อย ๆ
			//จนกว่า lp, rp จะไปอยู่ที่ตำแหน่งเดียวกัน แล้วก็สลับ position ของ rp,lp กับ pivot แค่นี้ก็ partition เสร็จแล้ว
			
			int leftPointer = lowIndex;
			int rightPointer = highIndex;
			
			while(leftPointer < rightPointer) {
				
				while(inputArray[leftPointer] <= pivot && leftPointer < rightPointer) {
					leftPointer++;
				}
				
				while(inputArray[rightPointer] >= pivot && leftPointer < rightPointer) {
					rightPointer--;
				}
				
				swap(inputArray, leftPointer, rightPointer);
			}
			
			swap(inputArray, leftPointer, highIndex); //Swap with pivot
			
			RecursiveQuickSort(inputArray, lowIndex, leftPointer - 1);
			RecursiveQuickSort(inputArray, leftPointer + 1, highIndex);
			
}