알고리즘 공부를 하고 있습니다.
Merge Sort를 공부해서 코드를 짜봤는데 성능이 너무 좋지않습니다.
100000 값을 계산하는데 대략 15초 가량 걸리는것 같아요.
[코드에서 컴퓨터에서 계산하는데 추가 로드가 걸리는 부분이 있을까요?]
[코드, test case배열은 첨부했습니다. 아래 붙여넣기는 했지만 가독성이 좋지 않네요.]


능력자님들 조언 부탁드립니다!


**잘못짠건지 결과값도 출력해보고, 루프마다 perf값을 +1해서 전체 몇번이나 루프를 도는지 체크도 해보았습니다.
100000 일때 모든 루프안에서 계산되는 값이 1668928으로 O(100000*log100000) = 1700000 이하로 정상적입니다.
컴퓨터가 1초에 10^9정도 계산하는것으로 알고있는데 10^6 정도면 바로나와야 하는거 아닌가요?
n:10 perf:34
n:14 perf:54
n:53 perf:307
n:256 perf:2048
n:595 perf:5521
n:999 perf:9965
n:1503 perf:15988
n:3951 perf:47267
n:4854 perf:59764
n:6912 perf:88576
n:8801 perf:115631
n:12042 perf:164246
n:25606 perf:376928
n:48140 perf:752844
n:62301 perf:993581
n:89139 perf:1473430
n:100000 perf:1668928
n:100000 perf:1668928
n:100000 perf:1668928
n:100000 perf:1668928



------------------------------------------
#include

#define N 100001 // 배열의 크기
int tmp[N];//병합을 위한 임시배열
int input[N];
long perf;

void ArrayMerge(int start, int end, int* arr)//두 배열의 병합함수
{
int mid = (start + end) / 2;//첫번째 배열의 끝 인덱스
int i = start; //첫번째 배열의 시작 인덱스
int j = mid + 1;//두번째 배열의 시작 인덱스

int k = start; //임시배열의 시작 인덱스
while (i <= mid && j <= end)//두 배열의 끝에 이르기까지 반복
{
perf++;
        if (arr[i] <= arr[j]) //첫번째 배열의 원소가 두번째 배열 원소보다 더 작거나 같으면
{
tmp[k] = arr[i]; //임시배열에 첫번째 배열 원소 추가
i++; //첫번째 배열 현재 인덱스 +1
        }
        else//두번째 배열의 원소가 더 작거나 같으면
{
tmp[k] = arr[j]; //임시배열에 두번째 배열 원소 추가
j++;//두번째 배열 현재 인덱스 +1
        }
        k++; //임시배열의 현재 인덱스 +1
        }

        //두 배열을 비교하고 남은 원소들을 임시배열에 추가
int t; //추가할 원소가 남은 배열의 시작 인덱스
int sch = 0;
        if (i > mid) //첫번째 배열의 원소가 모두 추가되었으면
t = j; //시작 인덱스를 두번째 배열의 현재 인덱스로 설정
else { //두번째 배열의 원소가 모두 추가되었으면
t = i;//시작 인덱스를 첫번째 배열의 현재 인덱스로 설정
sch = 1;
        }
        //남은 원소들을 임시배열에 추가
if (sch == 1) {
        //int numOfLeft = 0;
        for (k; k <= end; k++, t++) {
        perf++;
        tmp[k] = arr[t];
        }
        }
        else {
        for (k; k <= end; k++, t++) {
        perf++;
        tmp[k] = arr[t];
        }
        }

        //임시배열에서 원래 배열로 복사
for (k = 0; k <= end; k++)

        arr[k] = tmp[k];

}

void MergeSort(int start, int end, int*arr)
{
        int mid;
        if (start < end)
        {
        mid = (start + end) / 2; //배열의 중간 인덱스
MergeSort(start, mid, arr);//왼쪽 배열 분할
MergeSort(mid + 1, end, arr);//오른쪽배열 분할
ArrayMerge(start, end, arr);//병합
}
}

int main(void)
{
        int test_case;
        int T;
        int n;
        freopen("input.txt", "r", stdin);

        setbuf(stdout, NULL);
        scanf("%d", &T);

        for (test_case = 1; test_case <= T; ++test_case)
        {
        perf = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
        scanf("%d", &input[i]);
        }
MergeSort(0, n - 1, input);
        printf("n:%d perf:%u n", n, perf);
        }
        return 0;
}
-------------------------------------------------------------
[testcase] 올리려고 했는데 너무 길어서 올리기가 힘드네요.
100000 -> 1까지 역순데이터로 정렬해보시면 좋을것 같습니다.