[Algorithm] Merge Sort

• 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬
• 퀵소트와는 반대로 안정 정렬에 속함
• 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사
• 퀵소트와의 차이점
  • 퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
  • 합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

Implementation

void merge(int* arr, int start, int mid, int end) {
	int i = start;
	int j = mid + 1;
	int k = start;

	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			sorted[k++] = arr[i++];
		}
		else {
			sorted[k++] = arr[j++];
		}
	}

	// 아직 안 넣은 값 마저 넣어주기
	if (i > mid) {
		for (int t = j; t <= end; ++t) {
			sorted[k++] = arr[t];
		}
	}
	else {
		for (int t = i; t <= mid; ++t) {
			sorted[k++] = arr[t];
		}
	}

	for (int t = start; t <= end; ++t) {
		arr[t] = sorted[t];
	}
}

void mergeSort(int* arr, int start, int end) {
	if (start >= end) return;
	int mid = (start + end) / 2;
	mergeSort(arr, start, mid);
	mergeSort(arr, mid + 1, end);
	merge(arr, start, mid, end);
}

• Time Complexity : O(nlogn)
• Execution Time (sec) : 0.007 (원소 30000개 기준)

C++ 코드

---

ref :
병합정렬