합병 정렬 (Merge Sort)

- Simple, slow

• Bubble sort
• Insertion sort
• Selection sort

- Fast

• Quick sort
• Merge sort
• Heap sort

- O(N)

• Radix sort

 

 

정렬 중 이번엔 Merge sort에 대해 다뤄본다.

 

3단계를 거쳐 정렬이 이루어진다.

1) 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할한다.

    ex) 최대값을 구할 때, 리스트를 반으로 나누어 각각의 최대값을 구하여, 전체리스트의 최대값을 구하는 것과 비슷하다.

2) 정복: 각각의 작은 문제를 순환적으로 해결한다.

3) 합병: 작은 문제의 해를 합하여 (merge) 원래 문제에 대한 해를 구한다.

늘은 Simple하고 slow한 특성을 갖는 selection sort와 bubbl

 

mergeSort(A[], p, r) {//A[p...r]을 정렬한다
	if (p < r){ //p>=r인경우 -> 리스트의 개수가 0 또는 1, 즉 아무것도 안해도 됨 
		q < -(p + q) / 2; //p,q의 중간 지점 계산
		mergeSort(A, p, q);// 전반부 정렬
		mergeSort(A, q + 1, r);//후반부 정렬
		merge(A, p, q, r);//합병
	}
}
merge(A[], p, q, r) {
	정렬되어 있는 두 배열 A[p,...,q]와 A[q+1,...,r]을 합하여
	정렬된 하나의 배열 A[p,...,r]을 만든다.
}

 

---

그렇다면, 정렬된 리스트를 어떠한 방식으로 합병(merge)해야할까?

1) 모두 1개로 쪼개진 리스트로 만들어진 상태라고 가정하자.(initial sequence)

2) i: 1번째 리스트 중 첫번째 값

     j: 2번째 리스트 중 첫번째 값

     k: 전체 리스트 중 첫번째 값

- 위와 같이 i와 j를 이용해 비교하며 새로운 배열의 값 k를 채워나가면 합병 정렬이 완료 된다.

void merge(int data[], int p, int q, int r) {
	int i = p, j = q + 1, k = p;
	int tmp[data.length()];
	while (i <= q && j <= r) {
		if (data[i] <= data[j])
			tmp[k++] = data[i++];
		else
			tmp[k++] = data[j++];
	}
	//쪼개진 리스트 중 하나가 끝에 다다른 경우
	while (i <= q)
		tmp[k++] = data[i++];
	while (j <= r)
		tmp[k++] = data[j++];
	for (int i = p; i <= r; i++)//tmp리스트를 다시 data리스트로 옮김.
		data[i] = tmp[i];
}

---

merge sort의 시간복잡도

-> T(n)= 2* T(n/2) + n = O(nlogn)