고급 정렬(1) - 병합정렬(merge sort)

• 재귀 용법을 활용한 정렬 알고리즘

 

• 과정
  • 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔
  • 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬함
  • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병
  • 두 개의 함수를 통해 작업이 수행됨

 

• 첫 번째 함수: 리스트를 분리하고 각 분리된 리스트를 두 번째 함수를 통해 병합하여 리턴
  • 리스트의 중간 인덱스를 기준으로 왼쪽, 오른쪽 리스트로 분리
  • 각 분리된 리스트는 재귀 함수로 동일한 과정 진행 - 정렬 및 합병 과정
  • 최종적으로 합병된 리스트가 리턴됨

 

• 두 번째 함수: 첫 번째 함수에 의해 쪼개진 리스트를 정렬된 하나의 리스트로 리턴
  • 분리된 왼쪽, 오른쪽 리스트가 파라미터이며, 두 리스트를 정렬된 하나의 리스트로 만들어 반환
  • 작업 시작 시, 각 리스트의 첫 번째 값의 인덱스가 각각의 인덱스가 됨
  • 각 리스트의 인덱스에 해당하는 값끼리 비교 수행, 작은 값을 정렬 리스트이 input
  • input된 멤버를 보유했던 리스트의 인덱스 값은 1이 증가되며 어느 한 쪽의 멤버가 없어질 때까지 비교 및 삽입 작업 수행
  • 어느 한 쪽의 리스트가 빈 배열이 되면(즉 모든 요소들이 정렬 리스트에 input 된 경우)
  • 다른 한 쪽의 리스트에서 멤버 input 및 인덱스 증가 작업을 반복하여 남은 모든 요소를 정렬 리스트에 input함
  • 양쪽 모든 리스트의 요소를 다 정렬 리스트에 input 완료했다면 정렬 리스트를 반환

 

function mergeSplit(data) {
  if (data.length <= 1) {
    return data;
  }
  const medium = Math.floor(data.length / 2);
  const left = mergeSplit(data.slice(0, medium));
  const right = mergeSplit(data.slice(medium))

  return merge(left, right);
}

function merge(left, right) {
  const merged = [];
  let leftPoint = 0;
  let rightPoint = 0;

  // case1: 배열 멤버가 left와 right에 모두 남아있을 때
  while (left.length > leftPoint && right.length > rightPoint) {
    if (left[leftPoint] > right[rightPoint]) {
      merged.push(right[rightPoint]);
      rightPoint++;
    } else {
      merged.push(left[leftPoint]);
      leftPoint++;
    }
  }
  // case2: 배열 멤버가 left에만 남아있을 때
  while (left.length > leftPoint) {
    merged.push(left[leftPoint]);
    leftPoint++;
  }
  // case3: 배열 멤버가 right에만 남아있을 때
  while (right.length > rightPoint) {
    merged.push(right[rightPoint]);
    rightPoint++;
  }

  return merged;
}

 

출처: 패스트캠퍼스 알고리즘 / 기술면접 올인원 패키지