merge sort는 확실히 시간복잡도에서 가장 우수한 편에 속하긴 하지만, 그건 어디까지나 분할 정복이 제대로 이루어질 때의 얘기입니다.

분할되는 태스크는 그 크기가 작아져야하는데, 위 코드에선 분할되어 작아지는 태스크 안에서 크기 N짜리 배열을 두 개나 만들고 초기화하고 있어 실제로는 전혀 작아지지 않고 있습니다.

위 정렬 방식의 시간복잡도를 보다 엄밀히 분석해보면, 실제 시간복잡도는 N^2 혹은 그 이상입니다.

그리고 재귀로 몇 단계씩 호출되어 들어가는 함수 내에서 저렇게 배열을 크게 만들면 스택 터질 것 같습니다... 

merge()에서 a와 b를 초기화하는데 각각 1000000번의 대입 연산이 필요하고, 이를 999999번 호출하므로 결과적으로는 O(N^2)와 다를 게 없습니다.

a와 b의 크기를 감당 가능할 정도로 줄이든, 전역 변수로 빼든 해서 초기화 연산을 줄이세요.

함수가 여러 번 호출되면서 변수도 여러 번 선언되는 부분을 간과했군요! 두 분 다 정말 감사합니다. 덕분에 해결했습니다!!