'병합정렬' 태그의 글 목록

병합 정렬 (merge sort)는, 분할을 하고, 정복하는 단계에서 정렬된 두 배열을 합치는 식으로 동작합니다. 추가적인 공간이, 배열 크기만큼 필요하다는 것을 생각해 본다면, 메리트가 없을 수도 있어요. 실제로, Quick이 merge보다 빠르다는 이야기도 있을 정도이니까요. 그런데, Quick이 최악의 경우에 제곱에 비례하는 시간이 걸리는 반면에, merge는 그렇지 않아요. depth가 logn이기 때문입니다. 실제로 머지는 최악이던 최선이던 O(nlogn)에 동작합니다. 버블이나, insertion, selection sort에 비하면 꽤 빠릅니다. 일단 정렬이 된 두 부분 배열이 있다고 해 봅시다. 즉, le에서 mid까지 정렬이 되어 있고, mid+1부터 ri까지 sorting이 되어 있습니..