병합 정렬(Merge Sort) [의미] 전체 원소를 하나의 단위로 분할한 후 분할한 원소들을 다시 병합하는 정렬 [특징] 분할 단계와 병합 단계로 나뉘어져 있으며, 분할 단계는 시간복잡도에 포함하지 않음. Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬) [Big O] Best - O(nlog₂n) Worst - O(nlog₂n) [장점] 데이터의 분포에 영향을 적게 받음. 크기가 큰 레코드를 정렬할 경우 연결 리스트(Linked List)를 사용한다면, 링크 인덱스만 변경됨으로 데이터의 이동이 엄청나게 적어지고 In-Place정렬로 구현할 수도 있다. [단점] 레코드를 배열(Array)로 구현하면 Not-In-Place 정렬이 되며 추가적인 별도의 메모리를 필요로 하게 된다. [구현] ..