기본 알고리즘 - MergeSort

1. MergeSort 개요

 - 입력을 분할한다.

 - 각 Partion 에 대해 다시 Sort 한다.

 - Sort 된 Partion 에서 가장 작은 값을 먼저 저장한다.

 

 

2. 기본 알고리즘

MergeSort (A, p, q)

{

if( p == q)

return ;

middle= (p+q)/2;

MergeSort (p,middle);

MergeSort (middle+1, q);

Merge(A,p,q,middle);

}

 

 

Merge(A,p,q,middle)

{

leftIdx=0, rigthIdx=0, idx = 0 ;

for i=p to middle

tmpLef[idx++]=A[i];

tmpLeft[idx]=MAX;

for i=middle to q

tmpRight[idx++]=A[i];

tmpRight[idx]=MAX;

 

for i=p to q

if(tmpLeft[leftIdx] < tmpRight[rightIdx])

A[i] = tmpLeft[leftIdx++];

else

A[i] = tmpRight[rightIdx++];

     

}

3. 구현

private void mergeSort(int[] A, int p, int q)
	{
		if (p == q)
		{
			return ;
		}
		int middle = (p+q)/2;
		
		mergeSort(A, p,middle); 
		mergeSort(A, middle+1, q);
		merge(A, p,q, middle); 
	}
	
	private void merge(int[]A, int p, int q, int m)
	{
		int i ;
		int[] tmpLeft = new int[m-p+1+1];	// m 포함		
		int[] tmpRight = new int[q-m+1];		//m 미포함
		
		for( i = 0 ; i < tmpLeft.length-1 ; i++)
		{
			tmpLeft[i] = A[p+i];
		}
		tmpLeft[i] = Integer.MAX_VALUE;
		
		for( i = 0 ; i < tmpRight.length-1 ; i++)
		{
			tmpRight[i] = A[m+1+i];
		}
		
		tmpRight[i] = Integer.MAX_VALUE;
		
		int leftIdx = 0; 
		int rightIdx = 0; 
		
		for ( i =p ; i <= q; i++)
		{
			if( tmpLeft[leftIdx] <= tmpRight[rightIdx] ) {
				A[i] = tmpLeft[leftIdx++] ;
			} else{
				A[i] = tmpRight[rightIdx++] ;
			} 
		}
	}