정렬알고리즘 - Merge Sort (병합정렬) | C, Python 코드 구현

출처:  https://en.wikipedia.org/wiki/Merge_sort

📌Merge Sort 병합 정렬

1. 분할(Divide): 정렬하고자 하는 리스트를 같은 크기의 2개의 리스트로 분할한다.
2. 정복(Conquer): 각 리스트를 정렬하고, 각 리스트의 크기가 더 분할 가능하다면 재귀적으로 분할 정복을 반복한다.
3. 결합(Combine): 정렬된 각 리스트를 하나의 리스트로 합친다.

 

 

📌puedo code 구현

split

• 만약 리스트 개수가 한 개이면 해당 값 리턴
• 그렇지 않으면 리스트를 left와 right로 나누기 (재귀용법을 이용하여 리스트 개수가 한 개가 될 때까지(더이상 쪼갤 수 없을 때까지))
  • left = split(앞)
  • right = split(뒤)
• left와 right 합치기

merge

• 정렬된 숫자들을 넣을 리스트 생성 (sorted)
• left와 right의 비교할 데이터를 가리키는 각각의 index를 저장할 변수 생성 (left_index, right_index)
• while left_index < len(left) or right_index < len(right): (아직 비교할 데이터가 남아있으면)
  • left나 right 둘 중 하나가 이미 순회하여 비교가 완료되었다면 그 반대쪽 데이터를 그대로 뒤에 넣고 해당 index +1. left, right 각각은 모두 정렬완료된 리스트이기 때문
  • left[left_index]가 right[right_index]보다 작으면 left[left_index]를 sorted에 추가
  • right[right_index]가 right[right_index]보다 크면 right[right_index]를 sorted에 추가

 

📌알고리즘 구현(C)

int sorted[N];


void merge(int *list, int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  while(i<=mid && j<=right){
    if(list[i]<=list[j])
      sorted[k++] = list[i++];
    else
      sorted[k++] = list[j++];
  }

  while (i <= mid)
	  sorted[k++] = list[i++];

  while (j <= right)
	  sorted[k++] = list[j++];

  for(l=left; l<=right; l++)
    list[l] = sorted[l];
}


void merge_sort(int *num_arr, int left, int right){
	int mid;
	if (left < right) {
		mid = (left + right) / 2; 
		merge_sort(num_arr, left, mid);
		merge_sort(num_arr, mid+1, right);
		merge(num_arr, left, mid, right);
	}
}

merge_sort()와 merge()가 재귀적으로 호출되는 과정

 

📌알고리즘 구현(Python)

def merge_sort(num_list):
    i, j, k = 0, 0, 0
    if len(num_list) == 1:
        return num_list


    mid = len(num_list) // 2
    left_list = num_list[:mid]
    right_list = num_list[mid:]
    merge_sort(left_list)
    merge_sort(right_list)

    while (i < len(left_list) and j < len(right_list)):
        if (left_list[i] <= right_list[j]):
            num_list[k] = left_list[i]
            i += 1
        else:
            num_list[k] = right_list[j]
            j += 1
        k += 1

    while (i < len(left_list)):
        num_list[k] = left_list[i]
        i += 1
        k += 1

    while (j < len(right_list)):
        num_list[k] = right_list[j]
        j += 1
        k += 1

    return(num_list)

 

📌시간복잡도

병합 정렬의 시간복잡도는 $O(n log(n))$이다. 우선, 전체 배열을 쪼갤 수 없을 때까지 계속 분할하는 과정까지 $log(n)$번의 함수가 호출된다. (즉, merge_sort() 함수가 호출되는 것이 $lon(n)$번이다.)

그리고 각각 2개의 리스트로 분할된 단계에서 병합을 할 때, 조건 비교를 하며 while문을 총 $n$번 돌게 된다.

따라서 병합 정렬의 시간복잡도는 $O(n log(n))$으로 정의할 수 있다.