(정렬) 합병정렬 코드

시간 복잡도 : O(nlogn)

pseudo code

MergeSort(A,p,q)
input : A[p]~A[q]
output : 정렬된 A[p]~A[q]
--------------------------------------
if ( p < q ){
    k = [( p + q ) / 2]
    MergeSort(A,p,k)
    MergeSort(A,k+1,q)
    A[p] ~ A[k]와 A[k+1]~A[q]를 합병함.
}

 

c 코드

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

void MergeSort(int *A,int p, int q) {
	if (p < q) {
		int k = (p + q) / 2;
		MergeSort(A,p,k);
		MergeSort(A, k + 1, q);

		int left, right,n=0;
		left = p; right = k+1;
		int tmp[600001] = { 0, };
		while (left <= k && right <= q) {
			if (A[left] < A[right]) {
				tmp[n++] = A[left++];
			}
			else {
				tmp[n++] = A[right++];
			}
		}
		while (right <= q) {
			tmp[n++] = A[right++];
		}
		while (left <= k) {
			tmp[n++] = A[left++];
		}
		for (int i = 0; i < n; i++) {
			A[p + i] = tmp[i];
		}
	}
}


int main() {
	clock_t start, end;
	int numbers[600001] = { 0, };
	int num = 0;
	scanf_s("%d", &num);
	for (int i = 0; i < num; i++) {
		int tmp = rand() % 100 + 1;
		numbers[i] = tmp;
	}
	start = clock();
	MergeSort(numbers, 0, num-1);
	end = clock();
	printf("총 소요시간 : %.3f\n", (float)(end - start) / CLOCKS_PER_SEC);
	system("pause");
	return 0;
}

 

실행시간

8개 : 0.005

100개 : 0.022

10,000개 : 1.496

60,000개 : 8.461

600,000개 : 87.604

1,000,000개 : 268.532