병합 정렬(Merge Sort)

병합 정렬은 여러 개의 정렬된 자료의 집합을 겹합하여 한 개의 정렬된 집합으로 만드는 정렬 방법이다. 병합 정렬은 전체 원소들에 대해서 수행하지 않고 부분집합으로 분할(Divide)하고 각 부분집합에 대해서 정렬 작업을 완성(Conquer)한 후에 정렬된 부분집합들을 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다.

2개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 2-way 병합이라 하고, n개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법을 n-way병합이라고 한다.

2-way 병합 정렬은 다음과 갑ㅌ으 작업을 반복 수행하면서 완성한다.

1) 분할(Divide) : 자료들을 같은 크기의 부분집합 2개로 분할한다.

2) 정복(Conquer) : 부분집합에 있는 원소들을 정렬한다. 부분집합의 크기가 충분히 작지않으면 순환 호출을 이용하여 다시 분할한다.

3) 결합(Combine) : 정렬된 부분집합들을 하나의 집합으로 결합한다.

시간복잡도 : O(nlog2n)

public class mergeSort {

static int sorted[]=new int[30];

public static void main(String[] args) {

int a[]={69,10,30,2,16,8,31,22};

int size=a.length;

for(int i=0  ; i<a.length ; i++){

System.out.print(a[i]+" ");

}

System.out.println("\n");

mergesort(a,0,size-1);

}

public static void mergesort(int a[], int m, int n)

{

int middle;

if(m<n){

middle=(m+n)/2;

mergesort(a,m,middle);

mergesort(a,middle+1,n);

merge(a,m,middle,n);

}

}

public static void merge(int a[], int m, int middle, int n)

{

int i,j,k,t;

i=m;

j=middle+1;

k=m;

while(i<=middle&&j<=n){

if(a[i]<=a[j]){

sorted[k]=a[i];

i++;

}

else{

sorted[k]=a[j];

j++;

}

k++;

}

if(i>middle) for(t=j ; t<=n ; t++,k++) sorted[k]=a[t];

else for(t=i ; t<=middle ; t++,k++) sorted[k]=a[t];

for(t=m ; t<=n ; t++) a[t]=sorted[t];

for(int l=0  ; l<a.length ; l++){

System.out.print(a[l]+" ");

}

System.out.println("\n");

}

}