합병정렬 (1) 썸네일형 리스트형 [Sorting 03] Merge Sort의 개념 및 구현 들어가며 복잡한 정렬 알고리즘 중에서 가장 간단하다는 합병정렬(merge sort)에 대해 포스팅해 볼 것이다. 알고리즘을 막 공부하기 시작했을 때, merge sort를 구현하다가 막혀 며칠을 끙끙댔던 기억이 있다. 이제 그 때보다는 실력이 조금 나아졌으리라 기대하면서 포스팅을 시작해본다. 개념 및 특징 존 폰 노이만이 1945년에 개발했다. 분할정복(divide and conquer) 알고리즘 중 하나이다. 결과를 임시 배열에 저장했다가 다시 복사하는 과정이 발생하므로, 추가적인 메모리 공간도 요구되고 배열 복사에 시간이 소요된다. 최악 시간 복잡도: O(NlogN) 최선 시간 복잡도: O(NlogN) 평균 시간 복잡도: O(NlogN) 알고리즘 리스트의 길이가 1 이하면 이미 정렬된 것으로 본다. .. 이전 1 다음