[알고리즘] 병합 정렬

백준 2751번 문제를 풀면서 O(n log n)의 시간복잡도를 가진 정렬 알고리즘을 구현해야 했기에 그 중 하나인 병합 정렬에 대해 알아보겠습니다.

시작하기에 앞서..

먼저, 알고리즘에 있어서 효율성과 단순성은 안타깝게도 상충됩니다.

간단하고 빠른 코드가 있다면 정말 좋겠지만.. 안타깝게도 그렇지 않다는 것을 미리 말씀드리고, 두려워하지 마시길 바라며 시작하겠습니다.

병합 정렬은 간단한 정렬 알고리즘에 비해 확실히 더 어렵고, 더 길며, 코드가 길지 않더라도 더 이상합니다.

이것은 보통 인간들이 생각하는 방식과는 다르기 때문입니다.

병합 정렬의 등장

어느것을 배우던 우리는 조금 더 깊이 알아야 할 필요가 있습니다.

1948년 컴퓨터 과학자이자, 수학자, 여러 방면에서 역사의 큰 획을 그은 천재 중의 천재 폰 노이만이 EDVAC이라고 하는 컴퓨터에서 사용하는 23페이지 분량의 최초의 병합 정렬 프로그램을 작성하였습니다.

병합 정렬

개념잡기

• 병합 정렬이란 분할, 정렬, 병합 이 세 가지를 활용합니다.
• 0, 1개의 요소 배열은 이미 정렬되어 있다는 점을 활용합니다.

배열을 더 작은 배열로 계속해서 분할하여 0이나 1개의 요소를 가진 배열로 만듭니다.

분할이 끝나면 정렬하면서 병합하는 과정으로 정렬이 이루어집니다.

이 과정을 도식화한다면 다음과 같은 형태가 나타납니다.

알고리즘으로 구현하기

먼저 코드를 작성하기 이전에 의사 코드부터 작성하도록 하겠습니다!

구현하기에 앞서.
정렬된 두 배열 병합을 담당할 함수를 먼저 구현하는 게 좋습니다.
정렬된 두 배열이 주어질 때, 이 헬퍼 함수는 정렬된 새 배열을 만듭니다.

헬퍼 함수마지막에 반환할 빈 배열을 만듭니다.

const result = []

배열 두 개의 요소를 비교해야하기 때문에 각 배열의 인덱스를 참조할 변수 i와 j가 필요합니다. 이는 While문에서 활용하기 좋습니다.

const firstArr = [1, 3, 5, 7, 9];
const secondArr = [2, 4, 6, 9, 10, 12];

두 배열의 가장 작은 값부터 비교를 합니다. firstArr[i], secondArr[j]
둘 중 작은 값을 새로운 배열에 넣어주고, 해당 값을 가진 배열의 다음 인덱스와 비교를 합니다. 
firstArr[i+1], secondArr[j] // result에 담긴 값 : [1]

다시 둘 중 작은 값을 새로운 배열에 넣어주고, 해당 값을 가진 배열의 다음 인덱스와 비교를 합니다. 
firstArr[1], secondArr[i+1] // result에 담긴 값 : [1, 2]

이를 반복하다보면 두 배열의 길이가 달라 비교 할 대상이 없는 때가 생깁니다.
두 배열은 각각 같은 방식으로 정렬된 배열이기때문에 마지막으로 남는 값들은 자동적으로 앞의 수보다 크기 때문에 result 배열의 뒤로 들어가게 됩니다.

의사 코드가 다 파악이 되었으니 javascript로 구현해보겠습니다.

function merge(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;
  while(i < arr1.length && j < arr2.length) {
    if(arr2[j] > arr1[i] {
       result.push(arr1[i]);
       i++;
  	} else {
      	result.push(arr2[j];
        j++;
    }
  }
  while(i < arr1.length) {
    result.push(arr[i])
    i++;
  }
  while(j < arr2.length) {
    result.push(arr[j])
    j++;
  }
  return result;
}


function mergeSort(arr) {
  if(arr.length <= 1) return arr;
  
  let mid = Math.floor(arr.length/2);
  let left = mergeSort(arr.slice(0,mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

병합 정렬은 이런식으로 작성 할 수 있습니다. 재귀의 개념만 이해하고 있다면 코드를 파악하기 어렵지 않다고 생각합니다.

병합 정렬의 빅오 (Big O)

병합 정렬은 입력값이 이미 정렬 되어있는 경우, 혹은 아예 역순인 경우에도 영향을 받지 않습니다.
따라서 항상 변하지 않는 O(n log n)의 시간복잡도를 가지며 시간복잡도 순위는 다음과 같습니다.

맺는 말

백준 문제를 해결하기 위해 이렇게까지 공부했던 적은 이번이 처음이다. 모르는 문제가 생겼을 때 정답만 긁어왔던 내가 점점 배움에 익숙해지는 것이 느껴져 뿌듯하다. 항상 배우며, 한 걸음씩 더 깊이 파고드는 습관을 들여보자.
몰랐는데 백준 2751은 병합 정렬로 풀 수 없는 문제였다.. 문제 설명엔 병합 정렬 방법도 된다면서 ㅠㅠ 덕분에 퀵 정렬까지 공부 할 수 있겠다. 오히려 좋아