머지소트(MergeSort) 구현해보기 JAVA(자바)

병합 정렬은 분할 정복이라는 알고리즘에 근거하여 만들어진 정렬 방법이다.

 

우선은 분할의 과정으로 데이터를 둘로 나누고 하나씩 구분이 될 때까지 진행을 한다.

 

분할이 완료되었다면 작은 순서대로 하나씩 b 배열에 추가해서 순서를 맞추고 a배열에 넣어준다.

 

별도의 배열이 하나 더 필요하다는 특징이 있다.

 

 

	public class main {
	public static void main(String[] args) {
	int[] a = new int[4];
	a[0] = 3;
	a[1] = 1;
	a[2] = 5;
	a[3] = 4;
	mergeSort(a, 0, 3);
	for(int A : a)
	System.out.print(A + " ");
	}
	private static void mergeSort(int[] a, int left, int right) {
	if(left < right) {
	int mid = (left + right) / 2;
	mergeSort(a,left,mid);
	mergeSort(a,mid+1,right);
	merge(a,left,mid,right);
	}
	}
	private static void merge(int[] a, int left, int mid, int right) {
	int lidx = left;
	int ridx = mid+1;
	int[] b = new int[a.length];
	int bidx = left;
	while(lidx <= mid && ridx <= right) {
	if(a[lidx] <= a[ridx]){
	b[bidx] = a[lidx];
	lidx += 1; bidx +=1;
	}
	else {
	b[bidx] = a[ridx];
	ridx += 1; bidx +=1;
	}
	}
	if(lidx > mid) {
	for(int i = ridx; i<= right; ++i,++bidx)
	b[bidx] = a[i];
	}
	else {
	for(int i = lidx; i<= mid; ++i, ++bidx)
	b[bidx] = a[i];
	}
	for(int i=left; i<=right; ++i)
	a[i] = b[i];
	}
	}

view raw .java hosted with ❤ by GitHub