병합 정렬(Merge Sort)

오름차순 Top-Down Merge Sort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 100

void merge(int arr[], int temparr[], int lo, int mid, int hi) {
	int i, j, k;

	for (k = lo; k <= hi; k++)
		temparr[k] = arr[k];

	i = lo; j = mid + 1;
	for (int k = lo; k <= hi; k++) {
		if (i > mid) arr[k] = temparr[j++];		// mid+1 ~ high 까지 남은 배열 복사 (left 파트 확인 끝)
		else if (j > hi) arr[k] = temparr[i++];		// lo ~ mid 전 까지 남은 배열 복사 (right 파트 확인 끝)
		else if (temparr[j] < temparr[i]) arr[k] = temparr[j++];
		else arr[k] = temparr[i++];
	}
}

void mergeSort(int arr[], int temparr[], int lo, int hi) {
	if (hi <= lo) return;
	int mid = (lo + hi) / 2;
	mergeSort(arr, temparr, lo, mid);
	mergeSort(arr, temparr, mid + 1, hi);
	if (arr[mid] < arr[mid + 1]) return;	// 이미 정렬되어 있으면 병합하지 않음
	merge(arr, temparr, lo, mid, hi);	// 병합
}

void printArray(int arr[]) {
	int i;

	for (i = 0; i < MAX_SIZE; i++) {
		if (i != 0 && i % 10 == 0) puts("");
		printf("%d ", arr[i]);
	}
}

int main() {
	int i;
	int arr[MAX_SIZE], temparr[MAX_SIZE];
	srand(time(NULL));

	for (i = 0; i < MAX_SIZE; i++) {
		arr[i] = rand() % 100;
	}

	mergeSort(arr, temparr, 0, MAX_SIZE-1);
	printArray(arr);
}

실행 결과