합병정렬 일반형

합병(병합)정렬은 분할 정복 알고리즘 중 하나이며, 일반적으로 데이터의 안정성을 훼손하지 않는다.

분할 정복은 크게 3단계로 구성된다.

 

1) 분할(Divide): 최소단위까지 문제를 분할한다.

2) 정복(Conquer): 최소 단위 문제를 각각 해결하여 정복한다.

3) 결합(Combine): 최소 단위 문제에 대한 결과를 원래 문제에 대한 결과로 조합하여 해결한다.

 

분할-정복의 3단계:

• 1단계: 배열을 계속해서 반으로 자른다. 원소가 1개가 될 때가지 자른다.
• 2단계: 자른 순서의 역순으로 한 쌍씩  값을 비교하여 합쳐간다.
• 3단계: 하나의 배열이 될 때까지 2단계 과정을 반복한다.

 

function mergeSort(arr) {
    // 배열의 길이가 1 이하면 정렬이 필요없으므로 그대로 반환
    if (arr.length <= 1) return arr;
    
    // 배열을 반으로 나누기 위한 중간점 계산
    const mid = Math.floor(arr.length / 2);
    
    // 배열을 둘로 나누기
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    
    // 재귀적으로 나눈 배열을 정렬하고 병합
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;
    
    // 두 배열을 비교하면서 작은 값을 결과 배열에 넣기
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] <= right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    // 남은 요소들을 결과 배열에 넣기
    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

 

 

- 합병 정렬은 모든 경우에 O(n log n)의 복잡도를 가지는 효율적인 알고리즘이다.

 

- 다만 공간 복잡도에 주의해야 한다. 입력배열을 저장할 추가 저장 메모리 공간이 필요한데, O(n)의 공간 복잡도가 발생하기 때문에 n이 매우 커지는 환경에서는 오버헤드가 생길 수 있다. 오버헤드는 환경에 따라 스택 오버플로우를 만들 수도 있다.

 

- 스택 오버플로우는 스택의 포인터가 스택의 경계를 넘어설 때 일어나는 현상이다. 프로그램이 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 스택이 오버플로우 된다고 하며 이 경우 일반적으로 프로그램 충돌이 발생한다.

 

- 자바스크립트 런타임인 Node.js의 경우 논블로킹 I/O를 제공하고 단일 스레드 이벤트 루프를 통해 동작한다. 구조적으로 하나의 무거운 동작을 처리하는 데 적합한 방식이 아니다. 이러한 환경에서는 공간 복잡도를 크게 차지하는 연산을 동작할 때 메모리 사용량이 급등하게 되며 서버가 꺼지는 경우를 쉽게 마주할 수 있다. 합병 정렬의 시간상 우위가 중요한지, 메모리 사용량의 안정성이 중요한지 고민해야 한다.

 

- 합병정렬은 각 원소가 정렬 후에도 본래의 순서를 유지하기 때문에 안정 정렬이다. 그러나 정렬 과정에서 임시로 만드는 배열은 별도의 메모리에 저장되고, 이 임시 배열은 제자리 정렬(in-place sort)은 아니다.

 

- 제자리 정렬은 공간 지역도와 관련이 있다. 메모리 상에 데이터를 쓴다는 것은 실제 컴퓨터 하드웨어 상 특정한 위치에 전자적인 신호가 저장됨을 의미한다. 이 때 컴퓨터는 1바이트씩 메모리를 할당하지 않고, 최소단위의 메모리를 할당한다. 아이맥의 경우 4바이트를 사용한다. 만약 사용자가 1바이트씩 100회의 입력작업을 요청하면 실제로는 400바이트의 공간에 각 1바이트씩을 할당하게 된다. 결과적으로 데이터가 연속적으로 저장돼 있지 않으므로 캐시 메모리 사용상 불이익이 있고, 또한 캐시메모리 역시 크게 잡힌다. 이 경우 메모리가 분산되어 있어 여러 지역을 사용하므로 "지역성이 나쁘다"고 표현한다. 반대로 메모리가 연속적으로 메모리가 연속적으로 붙어 있어 데이터 접근에 유리한 경우를 "지역성이 좋다"고 말한다.

 

- 제자리 정렬은 연속된 메모리를 한 번 받은 후에 재할당하지 않는다. 제자리 정렬이 아닌 방식에서는 새로운 메모리를 할당하는 과정이 반복되는데, 메모리의 연속성이 없어 지역성이 떨어진다.

 

참고도서: <쉽게 설명한 자바스크립트 알고리즘 - 한상훈>

 

 

합병정렬 함수의 시각화

 

 

 

merge함수의 시각화.

 

// 예시 1
// left.slice(leftIndex)는 [4, 7]을 반환
// right.slice(rightIndex)는 [8]을 반환

result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex))

// 단계별로 보면:
[1, 2, 3].concat([4, 7]).concat([8])
// 1단계: [1, 2, 3, 4, 7]
// 2단계: [1, 2, 3, 4, 7, 8]

// ---------------------------------------------

// 예시 2
left = [1, 5, 9]
right = [2, 3, 4]

// while 루프 후:
result = [1, 2, 3, 4]  // 여기까지 정렬됨
leftIndex = 1          // [5, 9]가 남음
rightIndex = 4         // 남은 것 없음

// concat 결과:
[1, 2, 3, 4].concat([5, 9]).concat([])
// = [1, 2, 3, 4, 5, 9]
// 여전히 정렬된 상태 유지!

 

 

 

예제1) 좌석 정렬

 

function mergeSort(arr) {

  if(arr.length <= 1) {
    return arr;
  }

  const mid = arr.length / 2;

  const left = arr.slice(0, mid);
  const right = arr.slice(mid);


  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {

  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while( leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++
    } else {
      result.push(right[rightIndex]);
        rightIndex++;
    }
  }

  return result
    .concat(left.slice(leftIndex))
    .concat(right.slice(rightIndex))
}

const VIPSeats = [
  'D5', 'B3', 'A1', 'D4', 'B1', 'A2', 'D1', 'C1', 'C5'
]

console.log(mergeSort(VIPSeats))


/*

[
  'A1', 'A2', 'B1',
  'B3', 'C1', 'C5',
  'D1', 'D4', 'D5'
]
*/

 

예제2)

 

/*
- 1부터 N까지 랜덤한 숫자가 무작위로 설정된 배열을 생성
- 해당 배열을 합병정렬하여 오름차순으로 정렬한다.
- 정렬된 배열의 숫자를 하나씩 사용하여 콘솔 로그를 출력
- 출력된 콘솔 로그에는 첫 번째 줄에는 숫자 1개(배열의 0번 인덱스 인자), 두 번째 줄에는 숫자 2개 (배열의 1번, 2번 인덱스 인자), 줄이 늘어감에 따라 숫자가 하나씩 더 표기되도록 한다.
- 마지막 줄까지 표기하고 만약 마지막 줄에 표기할 숫자가 부족하다면 표기된 마지막 숫자를 반복하여 트리를 완성한다.
- 트리 완성 후에 콘솔에 총 몇 줄의 트리가 제작됐는지 출력한다.
*/



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

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while(leftIndex < left.length && rightIndex < right.length) {
    if(left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

function makeRandomArr() {
  let arr = [];
  for(let i = 0; i < 100; i++) {
    const randomNo = Math.floor(Math.random() * 100 + 1);
    arr.push(randomNo);
  }
  return arr;
}


function printArr(arr) {
  let lineCount = 1;
  let index = 0;
  while(index < arr.length) {
      let line = '';  // 각 줄마다 새로운 빈 문자열로 시작
      for(let i = 0; i < lineCount; i++) {  // 현재 줄에 들어갈 숫자 개수만큼 반복
          if(index < arr.length) {
              line += arr[index] + " ";  // 숫자와 공백을 문자열에 추가
          }
          index++;
      }
      console.log(line);  // 완성된 줄 출력
      lineCount++;  // 다음 줄은 숫자를 하나 더 출력
  }
  console.log(`총 ${lineCount-1} 줄`);
}

const arr = makeRandomArr();
const sortedArr = mergeSort(arr);
printArr(sortedArr);


/*
1 
1 3 
3 4 5 
5 6 10 11 
12 12 16 16 17 
20 20 20 20 23 27 
27 30 31 31 32 34 35 
35 36 37 38 38 39 39 41 
42 46 48 48 48 48 49 49 49 
49 49 50 50 52 53 53 54 54 57 
57 58 58 60 61 62 63 64 65 66 66 
68 68 68 69 69 70 71 71 72 72 72 73 
74 75 78 78 79 83 84 84 89 89 89 89 89 
90 91 92 95 96 96 98 99 100 100 100 100 100 100 
총 14 줄

*/

 

 

 

 

 

 

아래와 같은 방식으로도 사용할 수 있다.

function mergeSortOptimized(arr) {
    const n = arr.length;
    // 한 번만 auxiliary 배열 생성
    const aux = new Array(n);
    
    function sort(low, high) {
        if (high <= low) return;
        
        const mid = Math.floor(low + (high - low) / 2);
        sort(low, mid);
        sort(mid + 1, high);
        merge(low, mid, high);
    }
    
    function merge(low, mid, high) {
        // auxiliary 배열에 복사
        for (let k = low; k <= high; k++) {
            aux[k] = arr[k];
        }
        
        let i = low, j = mid + 1;
        for (let k = low; k <= high; k++) {
            if (i > mid) arr[k] = aux[j++];
            else if (j > high) arr[k] = aux[i++];
            else if (aux[i] <= aux[j]) arr[k] = aux[i++];
            else arr[k] = aux[j++];
        }
    }
    
    sort(0, n - 1);
    return arr;
}