Intermediate Sorting Algorithms_Merge Sort

Udemy - 【한글자막】 JavaScript 알고리즘 & 자료구조 마스터클래스

Intermediate Sorting Algorithms

WHY LEARN THIS?

• The sorting algorithms we've learned so far don't scale well
• Try out bubble sort on an array of 100000 elements, it will take quite some time!
• We need to be able to sort large arrays more quickly

---

Merge Sort | 합병 정렬

• It's a combination of two things - merging and sorting!
• Exploits the fact that arrays of 0 or 1 element are always sorted
• Works by decomposing an array into smaller arrays of 0 or 1 elements, then building up a newly sorted array

- 폰 노이만이 최초의 합병 정렬 프로그램을 작성했습니다.
- 이를 뒷받침하는 개념은 실제로 합병과 정렬이라는 두 가지 조합으로 이루어져 있습니다. 사실 세 가지 조합이라고 볼 수도 있습니다. 분할, 정렬, 합병입니다. 이 세 가지가 모두 일어납니다.
- 0개 요소, 1개 요소 배열이 이미 정렬되어 있다는 점을 활용합니다. 만약 숫자 1로만 구성된 배열을 정렬해야 할 경우, 정렬되어 있다는 것을 알고 있습니다.
- 더 큰 배열을 나누고 더 작은 하위 배열로 정렬합니다. 이렇게 진행합니다. 0이나 1 요소 배열이 될 때까지 계속합니다. 계속 분할한 다음 다시 병합시킵니다.

https://visualgo.net/en/sorting

Merging Arrays Pseudocode

• Create an empty array, take a look at the smallest values in each input array
• While there are still values we haven't looked at...
  • If the value in the first array is smaller than the value in the second array, push the value in the first array into our results and move on to the next value in the first array
  • If the value in the first array is larger than the value in the second array, push the value in the second array into our results and move on to the next value in the second array
  • Once we exhaust one array, push in all remaining values from the other array

 

// Merges two already sorted arrays
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;
}
merge([100,200], [1,2,3,5,6])

mergeSort Pseudocode

• Break up the array into halves until you have arrays that are empty or have one element
• Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the full length of the array
• Once the array has been merged back together, return the merged (and sorted!) array

// Recrusive Merge Sort
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);
}

mergeSort([10,24,76,73])

Big O of mergeSort 

Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
O(n log n)	O(n log n)	O(n log n)	O(n)

- O(n log n)이 있습니다. O(n^2)보다 훨씬 낫습니다. log n이나 선형 n 시간만큼 좋지는 않지만 정렬 알고리즘에서는 사실상 최선입니다. 
-데이터에 구애받지 않는 정렬 알고리즘을 원한다면, 최선은 O(n log n)입니다. 그러니 합병 정렬은 좋습니다. 가장 최선일 때, 가장 나쁠 때, 평균적으로 모두 O(n log n)이죠.
- 보통은 시간 복잡도를 신경쓰지만, 공간 복잡도를 고려할 때는 확실히 먼저 배웠던 버블 정렬 등과 비교하면 합병 정렬이 더 많은 공간을 차지합니다.