123님 코드로 테스트를 해 보니까 진짜 시간 초과가 뜨네요.

MergeSort를 쓰신 거 같으신데요. Merge하는 알고리즘 자체는 맞습니다.

병합 정렬에 대해서 아실지도 모르겠지만요.

left에서 right까지 병합 정렬을 하는 경우, 다음과 같은 과정을 수행합니다.

(1) 먼저 left ~ mid까지를 병합정렬 합니다.

(2) 그 다음에 mid+1 ~ right까지를 병합정렬 합니다.

(3) 그리고 merge 합니다.

29번째 줄에서 30번째 줄을 봅시다.

(1) sort( age, name, 0, mid );  // 0 ~ mid까지 정렬합니다.

(2) sort( age, name, mid + 1, right ); // mid+1 ~ right까지 정렬합니다.

어디서 잘못되었는지 보이시지요? 분명, left부터 right까지 정렬을 하면 되는데

(1)번 과정에서 0번째 원소부터 sorting하려고 하니.

(1)에서 sort 함수를 부르면 left = 0일 테고요. right = mid겠지요?

당연히 시간 초과가 나겠지요.

따라서 29번째 줄을

(1) sort( age, name, left, mid ); 

로 고쳐주시면 되겠습니다.

대충 n이 2^10인 경우.

RRRR RRRR RL 이렇게 호출을 하면요. (여기서 R은 Sort 함수 내의 2번째 Sort 함수, L은 Sort 함수 내의 1번째 Sort 함수)

초기 : 0 - 1024

R : 513 - 1024

R : 769 - 1024

R : 897 - 1024

R : 961 - 1024

R : 993 - 1024

R : 1009 - 1024

R : 1017 - 1024

R : 1021 - 1024

R : 1023 - 1024

이 상태에서 sort( age, name, 0, mid ); 를 호출하면 left가 0, right가 1023인 함수가 호출되겠네요.

호출 깊이가 어마어마해지는 것은 말할 것도 없겠네요. 호출 깊이가 (최악의 경우) NlogN급이라. 타임 아웃은 당연한 거고요. 

그에 따라서 불필요한 Merge 연산까지 생각한다면.

문제점 파악했습니다 감사합니다!