JavaScript Algorithm - mergeSort

문제설명

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 단 병합정렬을 사용해야 하며 조건은 다음과 같습니다.

• arr.sort()를 사용하면 안됩니다.
• 입력받는 배열은 중첩되지 않은 1차원 배열입니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

 

입출력 예시

let output = mergeSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

병합정렬이란?

• 병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘입니다. 병합 정렬은 다음과 같은 알고리즘을 사용합니다.
  1. N의 길이를 가진 배열 리스트를 1의 길이를 가진 "부분 리스트"가 N개 모인 것으로 취급합니다.
  2. 인접한 부분 리스트들을 정렬하여 2의 길이를 가진 부분 리스트로 병합합니다.
  3. 2의 길이를 가진 인접한 부분 리스트들을 4의 길이를 가진 부분 리스트로 합칩니다.
  4. 하나의 정렬된 리스트가 될 때까지 위 과정을 반복합니다.
  5. N이 홀수라면, 첫 번째 병합 때 1의 길이를 가진 부분 리스트를 남깁니다.
• 병합 정렬은 두 가지 방식으로 구현 가능합니다. 재귀적 접근(위->아래) 그리고 반복적 접근(아래->위)

 

풀이코드 

const merge = function (left, right) {
    //merged 배열 선언 
    let merged = [];
    //left, right 인덱스 변수 선언 
    let leftIdx = 0,
      rightIdx = 0;
    //size는 left와 right의 길이를 합친 총 길이 
    const size = left.length + right.length;
  
    //size크기만큼 반복 순회 
    for (let i = 0; i < size; i++) {
      //left 인덱스가 left 길이보다 크거나 같을 때
      if (leftIdx >= left.length) {
        merged.push(right[rightIdx]);
        rightIdx++;
        //right 인덱스가 right 길이 이상이거나 left배열의 left 인덱스가 right배열의 right인덱스 이하일 때 
      } else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
        merged.push(left[leftIdx]);
        leftIdx++;
      } else {
        //위 케이스 외에는 merged 배열에 right배열의 right 인덱스를 삽입 
        merged.push(right[rightIdx]);
        rightIdx++;
      }
    }
  
    return merged;
  };
  
  const mergeSort = function (arr) {
    //2미만일 때 arr 리턴 
    if (arr.length < 2) return arr;
    //middle에 arr 배열을 2등분한 것을 저장 
    const middle = parseInt(arr.length / 2);
    //left, right에 각각 middle을 기점으로 slice한 값을 저장함
    const left = mergeSort(arr.slice(0, middle));
    const right = mergeSort(arr.slice(middle));
    //merge 함수 호출값을 merged에 저장
    const merged = merge(left, right);
    return merged;
  };