머지소트는 분할정복알고리즘(Divide and Conquer)의 대표적인 예시로, 시간복잡도가 O(nlogn)인 매우 효율적인 정렬 알고리즘이다. 왜 머지일까? 일단 주어진 배열을 원소가 1인 부분배열들로 나뉠때까지 계속 분할하다가, 그 부분배열들을 다시 합치며(merge) 정렬하는 방식이기 때문이다. 이 과정에서 자기 자신을 호출하는 재귀적 방식으로 분할과 합치기(merge)를 진행한다는게 특징적인데, 한마디로 머리 꽤나 깨지는 알고리즘이라는 의미다.(^____^)컴퓨터 알고리즘 두번째 시간에는, 시간복잡도와 Big-O 표기법을 배웠고 정렬 알고리즘 중머지소트(merge sort)에 대해 배웠다. 분명 구현하는 코드는 짧고 간단했지만 왜 이 머지소트의 시간복잡도가 O(nlogn)이 되는지 너무 빨리 넘..
