merge sort

merge sort

병합정렬

vector<int> arr;
vector<int> temp;

void merge(int start, int mid, int end) {
	int p1 = start;
	int p2 = mid + 1;

	int k = start;

	while (p1 <= mid && p2 <= end) {
		if (arr[p1] <= arr[p2]) {
			temp[k] = arr[p1];
			k += 1; p1 += 1;
		}
		else {
			temp[k] = arr[p2];
			k += 1; p2 += 1;
		}
	}

	while (p1 <= mid) {
		temp[k] = arr[p1];
		k += 1; p1 += 1;
	}

	while (p2 <= end) {
		temp[k] = arr[p2];
		k += 1; p2 += 1;
	}

	for (int i = start; i <= end; i++) {
		arr[i] = temp[i];
	}
}

void merge_sort(int start, int end) {
	int mid = (start + end) / 2;

	if (start < end) {
		merge_sort(start, mid);
		merge_sort(mid + 1, end);
		merge(start, mid, end);
	}
}