Developer_Neo

앞서 있었던 퀵정렬은 피벗 값에 따라서 편향되게 분할 될 가능성이 있다는 것이다 그래서 최악의 경우 O(N^2)의 시간 복잡도를 가진다. 하지만 지금 배울 병합정렬은 편향되게 분할 될 가능성이 없다. 정확히 반 반씩 나누기 때문에 최악의 경우에도 O(N*logN)의 시간복잡도를 보장한다. Divdie and Conquer방식이라고도 배우는데 먼저 기존에 있는 배열들을 작게 작게 각각 하나씩 가질때 까지 나눈다는 것이다 그리고 merge할때 정렬해가면서 합친다는 것이다. 정렬을 할때 다른 배열을 생성하여 그 배열에 정렬해서 넣는것이다 방법은 나뉘어진 배열 2개에 대해 합치게 되는데 이때 각각 배열의 첫번째 인덱스의 값들을 비교해서 작은 것부터 생성한 배열에 넣는것이다. 위의 그림처럼 말이다 코드를 살펴보자..