합병정렬 (merge sort) 을 간단하게 알아보자 .

 

합병 정렬을 간단하게 설명하면?

분할 정복을 이용한 정렬!

 

1. 모든 숫자를 다 나눈 다음에 비교해 병합하는 분할, 정복 방식의 정렬입니다.
2. 각각의 배열이 독립적으로 분할될 때까지 반으로 나눕니다. 
3. 독립적으로 분할된 배열들(왼쪽그룹과 오른쪽 그룹)을 차례차례 비교해  정렬하고 합칩니다. 
4. 위의 과정은 분할과정과 정복과정으로 나누어지며 마침내 결합하는 순환적인 형태를 띠고 있습니다.

 

 

 

구현 과정 

import java.util.*;
public class Main {
	
	//합병과정 
	static void merge(int[] A, int left, int mid, int right) {
		int i=left;    //i는 왼쪽(시작)부터. (왼쪽 그룹)
		int j=mid+1;   //j는 mid+1부터.  (오른쪽 그룹)
		int[] temp= new int[right-left+1];    //정렬된 배열들을 임시로 저장할 곳.   
		int k=0; //temp배열의 인덱스 카운트.
		while(i<=mid && j<=right) {    //i나 j중 하나라도 배열의 범위를 넘어갔다는 것은 두 그룹간의 비교가 끝났다는 것.
			if(A[i]<=A[j]) {
				temp[k]=A[i];        //i인덱스 값이 j인덱스 값보다 작을경우 temp에 i인덱스값 저장.
				i++;                 //i는 다음 칸으로.
				k++;                 //k도 다음 칸으로. 
			}
			else {
				temp[k]=A[j];        //j인덱스 값이 i인덱스 값보다 작을경우 temp에 j인덱스값 저장.
				j++;                 //j는 다음 칸으로.
				k++;                 //k도 다음 칸으로. 
			}
		}
		
		while(i<=mid) {        //왼쪽 그룹이 오른쪽 그룹보다 값이 커서 아직 temp에 들어가지 않은 값이 있는 상황.
			temp[k]=A[i];
			i++;
			k++;
		}
		while(j<=right) {     //오른쪽 그룹이 왼쪽 그룹보다 값이 커서 아직 temp에 들어가지 않은 값이 있는 상황.
			temp[k]=A[j];
			j++;
			k++;
		}
		k--;    //while문을 빠져나가기 전에 k가 한번더 증가함. 배열길이초과 방지. 
		
		for(int l=0; l<=k; l++) {
			A[left+l] = temp[l];
		}
	}
	
	//합병정렬의 재귀함수 부분. 
	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);    //중간+1부터 끝까지 분할 
			merge(A, left, mid, right);  //분할된 왼쪽 그룹과 오른쪽 그룹을 정렬. 
		}
		else
			return;
	}
	
	public static void main(String[] args) {
		int[] A= {70, 20, 10, 80, 60, 90, 30, 40, 100, 50};
		
		for(int i=0; i<A.length; i++) {            //정렬 전 배열 출력 
			System.out.print(A[i]+" ");
		}
		System.out.println();
		
		mergesort(A,0,A.length-1);
		
		for(int i=0; i<A.length; i++) {
			System.out.print(A[i]+" ");
		}
}
}

 

 

시간 복잡도 

• Worst : O(nlogn)
• Average : O(nlogn)
• Best : O(nlogn)