Merge sort

합병정렬

입력받은 배열을 하나의 배열이 될 때까지 나눈 후, 정렬하여 다시 합병하는 알고리즘이다.

시간복잡도: O(n log n)
공간복잡도: O(n)

나누는 함수, 합치는 함수를 나누어 작성하였고, 재귀 함수를 이용하였다.

두개의 배열을 입력받아 정렬 후 합치는 함수

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

console.log(merge([12,35], [26,87])); // [12,26,35,87]

재귀함수를 이용해 배열을 나누고, 최종 배열을 리턴하는 함수

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)
}

console.log(mergeSort([10,24,76,73,72,1,9])); // [1,9,10,24,72,73,76]