합병 정렬 (merge sort)

뜬금 없지만, 알고리즘 공부를 시작했습니다.

공부한 내용을 기록을 위해 포스팅합니다. 

---

합병 정렬입니다. (merge sort)

구현이 약간 복잡하지만 퀵정렬, 힙정렬과 함께, 빠른 속도를 보여줍니다. 

#include <stdio.h>

int sorted[10];

void merge(int list[], int start, int end) {
	register int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start, j = mid + 1, k = 0;

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

	while (i <= mid) sorted[k++] = list[i++];
	while (j <= end) sorted[k++] = list[j++];

	for (i = start; i <= end; i++) {
		list[i] = sorted[i - start];
	}
}

void sort(int list[], int start, int end) {
	register int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;

	sort(list, start, mid);
	sort(list, mid + 1, end);
	merge(list, start, end);
}

int main() {
	int i;
	int list[10] = { 354, 22, 3232, 38, 342, 83, 827, 12, 92, 922 };

	sort(list, 0, 9);

	for (int i = 0; i < 10; i++) printf("%d ", list[i]);

	return 0;
}