정렬, 병합정렬 알고리즘

알고리즘 설명

<img alt="" src="https://static.podo-dev.com/blogs/images/2019/07/10/origin/TZ6DJE181224235510.PNG" style="width:260px">

병합정렬은 분할정복 기법을 사용한다.

전체원소가아닌 부분집합으로 분리 한후, 부분집합에 대하여 정렬을 수행한다.

정렬한 부분집합끼리 다시 결합하며, 정렬을 수행한다.

<br/>

복잡도

병합정렬 N개에 개수에 대하여 log2N번의 단계로 나누어진다.

각 단계별로 최대 N번의 비교를 하게된다.

따라서 복잡도는 O(Nlog2N) 이다.

<br/>

장단점

합병정렬의 가장 큰 장점은 입력데이터에 상관없이 최악, 평균, 최선 모두 O(Nlog2N) 복잡도를 가지는 것이다.

단점은 추가적인 공간이 필요하며, 비교적 이동연산이 많아 레코드가 큰 경우에는 많은 시간을 소비한다.

배열이 아닌 링크드 리스트로 구현 할 경우, 참조값만 변경하면 되기때문에 시간적 소비를 확 줄일 수 있어 이로 보완 할 수 있다.

<br/>

소스코드

public class MergeSort {
	int arr[] = { 10, 8, 1, 7, 3, 2, 15, 9, 5 };

	public void sort(int s, int mid, int e) {
		int k = s;
		int i = s;
		int j = mid + 1;
		int[] temp = new int[arr.length];

		while (i <= mid &amp;&amp; j <= e) {
			if (arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		}

		if (j > e) {
			for (int l = i; l <= mid; l++) {
				temp[k++] = arr[l];
			}
		} 
		
		if (i > mid) {
			for (int l = j; l <= e; l++) {
				temp[k++] = arr[l];
			}
		}

		for (int l = s; l <= e; l++) {
			arr[l] = temp[l];
		}

	}

	public void divide(int s, int e) {
		if (s < e) {
			int mid = (s + e) / 2;
			divide(s, mid);
			divide(mid + 1, e);
			sort(s, mid, e);
		}
	}

	public static void main(String[] args) {
		MergeSort mergeSort = new MergeSort();
		mergeSort.divide(0, mergeSort.arr.length - 1);
		System.out.print(Arrays.toString(mergeSort.arr));
	}
}

<br/>