병합 정렬(Merge Sort)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

① 병합 정렬(merge sort)은 분할 정복(devide and conquer)을 이용한 대중적인 정렬 알고리즘 중 하나이다.

  ㉠ 병합 정렬은 합병 정렬로도 불린다.

② 병합 정렬의 최악의 경우의 시간 복잡도는  O(nlog(n))으로 데이터의 크기가 큰 경우에 적절한 정렬 방법이다.

③ 병합 정렬의 기본 원리는 다음과 같다.

  ㉠ 정렬되지 않은 배열을 절반으로 나누는 행위를 배열의 사이즈가 1이 될 때까지 반복한다.

  ㉡ 사이즈가 같은 배열을 정렬하면서 배열을 하나로 합친다.

  ㉢ 합친 배열의 크기가 원래 배열이 될 때까지 ㉡를 반복한다.

 

④ 병합 정렬의 의사 코드(psuedo code)는 다음과 같다.

 

⑤ 병합 정렬은 크게 분할 과정과 병합 과정으로 나뉜다.

  ㉠ 분할 과정은 배열의 크기가 1이 될 때까지 재귀적으로 함수 mergeSort()를 호출한다.

 

  ㉡ 분할이 끝나면 함수 merge()를 호출한다.

 

    ⓐ 병합할 때는 각 배열의 크기를 고려해야 한다.

 

      (a) 왼쪽 배열의 길이가 0일 때는 오른쪽 배열을 모두 정렬한다.

 

왼쪽 배열의 길이가 0이고, 오른쪽 배열의 크기가 1일 때

왼쪽 배열의 크기가 0이고, 오른쪽 배열의 크기가 0일 때

      (b) 오른쪽 배열의 길이가 0일 때는 왼쪽 배열을 모두 정렬한다.

 

왼쪽 배열의 길이가 1이고, 오른쪽 배열의 크기가 0일 때

왼쪽 배열의 크기가 2이고, 오른쪽 배열의 크기가 0일 때

      (c) 둘의 길이가 같을 때는 양쪽 배열의 앞에서부터 더 큰 것을 골라오고, 한쪽 배열의 크기가 0이 되면, (a)와 (b) 중 해당하는 동작을 한다.

 

 

⑥ 병합 정렬의 시간 복잡도는 O(nlog(n))이다.

 

 

⑦ 병합 정렬의 코드는 다음과 같다.

 

⑧ 병합정렬은 안정한(stable) 정렬이다.