병합 정렬 : 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 시간복잡도는 O(nlogn)이다.
병합정렬의 핵심은 그룹별로 나누어 정렬과 병합을 반복하여 최종 정렬된 결과 값을 얻는 것이다. 위의 그림을 예시로 순서를 설명하겠다.
- 8개의 데이터를 두개씩 묶어 4개의 그룹으로 나누어 정렬을 진행한다
- 정렬된 데이터를 다시한번 네 개씩 묶어 2개의 그룹으로 나누어 정렬을 진행한다.
- 마지막으로 두 그룹의 데이터를 정렬을 통해 완성을 해야 하는데 여기서 다시한번 등장하는 개념이 투포인터이다.
- 각 그룹의 제일 앞 단의 인덱스를 각각 pointer1, pointer2라 하자.
- pointer1과 pointer2를 비교하여 작은쪽이 최종배열에 들어가게 되고 작은쪽 pointer를 한칸 옮기고 다시 비교를 진행한다.
- 이 로직을 반복하여 만약 한 그룹의 데이터가 모두 옮겨지면(포인터가 그룹 배열의 끝에 도달하면) 나머지 그룹의 데이터는 이미 정렬이 된 상태이므로 그대로 최종배열에 넣어주면 된다.
