[정렬] 삽입정렬, 병합정렬

버블정렬	O(N^2)	O(N^2)	코딩이 가장 손쉬움
카운팅 정렬	O(N+K)	O(N+K)	N이 비교적 작을 때만 가능
선택 정렬	O(N^2)	O(N^2)	교환의 회수가 버블, 삽입 정렬보다 작음
퀵 정렬	O(NlogN)	O(N^2)	최악의 경우 O(N^2)이지만, 평균적으로는 가장 빠름
삽입 정렬	O(N^2)	O(N^2)	N의 개수가 작을 때 효과적
병합정렬	O(NlogN)	O(NlogN)

삽입정렬

import java.util.Arrays;

public class InsertSort {
	public static void main(String[] args) {
		int[] arr = new int[] {69,10,30,2,16,8,31,22};

		for(int idx = 1; idx < arr.length; idx++) { // 삽입을 원하는 item
			int key = arr[idx];
			// System.out.println(key);
			// System.out.println(Arrays.toString(arr));
			int prev = idx - 1; 
			while(prev >= 0 && arr[prev] > key){
				arr[prev+1] = arr[prev];
				prev --;
			}
			arr[prev+1] = key; // prev는 temp 값보다 작은 값들 중 제일 큰 값의 위치를 가리키게 된다 
		}
		
		System.out.println(">>"+Arrays.toString(arr));
	}
}

병합정렬

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = new int[] {69,10,30,2,16,8,31,22};

	    mergeSort(arr, 0, arr.length - 1);
	}
	public static void mergeSort(int[] array, int left, int right) {
	    if (left < right) {
	        int mid = (left + right) / 2;
	 
	        mergeSort(array, left, mid);
	        mergeSort(array, mid + 1, right);
	        merge(array, left, mid, right);
	    }
	}
	 
	public static void merge(int[] array, int left, int mid, int right) {
	    int[] L = Arrays.copyOfRange(array, left, mid + 1);
	    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
	 
	    int i = 0, j = 0, k = left;
	    int ll = L.length, rl = R.length;
	 
	    while (i < ll && j < rl) {
	        if (L[i] <= R[j]) {
	            array[k] = L[i++];
	        } else {
	            array[k] = R[j++];
	        }
	        k++;
	    }
	 
	    while (i < ll) {
	        array[k++] = L[i++];
	    }
	 
	    while (j < rl) {
	        array[k++] = R[j++];
	    }
	}
}