[알고리즘] 병합정렬(Merge Sort)의 개념 with c++

병합정렬 또는 합병정렬은 정렬할 데이터들을 일단 반으로 쪼개고 각 각 정렬한 후 나중에 합치는 알고리즘이다.

비교 기반 정렬 알고리즘이고, 일반적인 방법으로 구현했을 때 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다.

매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적인 문제가 있다. 이에 병합 정렬의 시간 복잡도는 어떤 상황에서도 O(N*logN)이다. 

합병 정렬 예시(wikipedia)

 

병합 정렬 c++ 코드구현

#include<stdio.h>
#include<vector> //배열
#include<algorithm> 

using namespace std;

int a[101], b[101], c[300]; 

int main(){

	// 두 배열 합치기
	int n, m, i, p1=1, p2=1, p3=1;//포인트 
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", &a[i]);
	}
	
	scanf("%d", &m);
	for(i=1; i<=m; i++){
		scanf("%d", &b[i]);
	}
	//병합정렬 
	while(p1<=n && p2<=m){
		if(a[p1]<b[p2]){
			c[p3++]=a[p1++];
		}
		else{
			c[p3++]=b[p2++];
		}
	}
	//나머지 값들 넣기(둘 중하나만 해당) 
	while(p1<=n) c[p3++]=a[p1++];
	while(p2<=m) c[p3++]=b[p2++];
	
	for(i=1; i<p3; i++){
		printf("%d", c[i]);
	}
	
	return 0;	
    
}