[알고리즘] 정렬 - Merge Sort

Merge sort 합병정렬

- 재귀를 사용하는데 자꾸 까먹어서 정리한다.

- 크게 3부분으로 나뉜다. divide conquer combine

 

Divide: 배열을 mid를 중심으로 두 부분으로 나눈다. 배열 사이즈가 1이 될때까지 반복한다.

Conquer: 부분 배열을 정렬한다. 배열 size가 1일떄만 진행한다.

Combine: 정렬된 배열을 합병한다.

 

- 머지 소트를 하기 위해선 sorted된 리스트를 저장하기 위한 추가 배열이 필요하다. 

 

divide와 conquer: 배열 사이즈가 1일때까지 쪼갠다.

 

출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

 

merge: 정렬된 배열 2개를 하나의 sorted에 합친다. 

출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

시간 복잡도 O(NlogN)

 

#include <bits/stdc++.h>
#define MAX_SIZE 1000000 + 1

int arr[MAX_SIZE]; //원래 배열
int tmp[MAX_SIZE]; //카피 배열

void mergesort(int start, int end)
{

  if (start == end)
  {
    return; // 배열 사이즈가 1이면 리턴.
  }

  int mid = (start + end) / 2;

  mergesort(start, mid);
  mergesort(mid + 1, end); // 배열 사이즈가 1일때까지 쪼갠다.

  for (int i = start; i <= end; i++)
  {
    tmp[i] = arr[i]; //정렬을 위해 copy배열인 tmp를 만든다.
  }

  int point = start; //정렬된 배열의 인덱스
  int left = start;
  int right = mid + 1;

  while (left <= mid && right <= end) // 좌측 배열과 우측 배열의 값을 비교하여 sorted에 집어 넣는다.
  {
    if (tmp[left] < tmp[right])
    {
      arr[point] = tmp[left++];
    }
    else
    {
      arr[point] = tmp[right++];
    }
    point++;
  }

  while (left <= mid) //아직 정렬되지 않은 배열값들을 집어 넣는다.
  {
    arr[point++] = tmp[left++];
  }

  while (right <= end)
  {
    arr[point++] = tmp[right++];
  }
}

 

 

참고:

gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html