Merge Sort

[Algorithm] Merge Sort(병합 정렬) 1. 정의 데이터 배열의 원소를 반으로 나누고, 합쳐서 정렬하는 알고리즘 분할 정복을 사용 시간 복잡도 최선 : $O(nlogn)$ 평균 : $O(nlogn)$ 최악 : $O(nlogn)$ 2. 동작 과정 배열의 원소가 2개가 남을 때까지 이등분 한다. 2개의 원소를 반으로 나누어 각각 비교하여 정렬된 배열을 얻는다. 나머지 배열들을 병합하면서 정렬한다. 3. 장단점 장점 순차적인 비교로 정렬 일정한 속도 안정 정렬 LinkedList 정렬할 때 퀵 정렬 보다 효율이 좋음 LinkedList는 순차 접근을 해야하는데 퀵 정렬은 임의 접근이기 때문 단점 추가적인 공간이 필요 4. 코드 public void mergeSort(int[] arr, int l..