병합 정렬(Merge Sort)
키 포인트!! 일단은 반으로 나누고 나중에 합친다! 병합정렬은 퀵정렬가 달라 피벗 값이 없고 항상 반으로 나누는 특징이 있다 이렇게 반으로 쪼개는 단계때문에 O(Nlog N)이 된다. 또한 퀵 정렬과 다르게 정확히 반으로만 나누기 때문에 NlogN이 보장이 된다. 7 4 5 8 6 3 10 9 이런 배열이 있다고 가정하자 이것을 이제 2의 배수의 개수만큼 합친다. 근데 그때 오름차순으로 정렬하면서 합친다 2^1 : 4,7 5,8 3,6 9,10 2^2 : 4,5,7,8 3,6,9,10 2^3 : 3,4,5,6,7,8,9,10 이렇게 2의 승으로 진행되기 때문에 많은 데이터를 다룰 수가 있고 이 때문에 시간복잡도가 logN이다. 위의 표를 사각형으로보면 가로는 N이고 높이는 logN이다 따라서 총 시간 복..
2021. 11. 1.