글 읽기 - 분할정복 풀이 관련 질문

이 링크에서 공부하고 문제를 풀었는데, 글 끝부분에 보면

"여기서는 3번에서 일일이 정렬을 했기 때문에 O(nlog^2n)이라는 시간복잡도가 나왔지만, 병합 정렬의 아이디어를 이용해서 정렬을 O(n)에 하여 O(nlogn)에 할 수도 있습니다."

라는 언급이 있습니다.

병합 정렬의 아이디어를 사용한다는 것이 어떤 의미일까요?

블로그에 댓글 남길랬는데 블로그 주인장께서 최근에는 확인을 하지 않으시는 것 같아 여기에 질문을 올려봅니다.

머지 소트에서 길이가 A, B인 두 정렬된 리스트를 O(A+B)에 정렬된 상태로 합치는 방법을 사용하는걸 의미합니다. 저기 코드에서 40번째 줄을 머지 소트의 병합 과정으로 고치면 됩니다.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge