왜 Mergesort 보다 Quicksort를 사용할까?

• Mergesort가 Quicksort에 비해 항상 유리한 알고리즘이 아닌가?

• Locality

• Merge sort의 Locality

• Quick sort Locality

• 결론

Mergesort가 Quicksort에 비해 항상 유리한 알고리즘이 아닌가?

Quicksort에는 최악의 경우 O(n^2)의 시간복잡도를 가지고 있으며, 평균의 경우에는 O(nlogn)의 시간복잡도를 가지고 있습니다.

이에 비해, Mergesort는 최악의 경우와 평균의 경우 모두 O(nlogn)의 시간복잡도를 가지고 있는 굉장히 안정적인 알고리즘입니다. 

 

그래서 알고리즘을 배우면서 Mergesort가 훨씬 유리한 알고리즘 같은데, 왜 Quicksort가 일반적으로 더 많이 사용되는지 알고 싶어졌습니다. 

핵심을 말하면, 지역성(Locality) 때문입니다.

Locality

지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다.

 

Locality는 정렬 알고리즘의 평가 기준이 될 수 있습니다.

정렬하려고 하는 데이터들은 다른 페이지로 이동하는 것 없이, 자신의 페이지에서 계속 있는게 속도 측면에서 좋습니다. cache에 없는 다른 페이지로 이동해야 한다면, 결국 physical memory로 접근을 해야 하기 때문에 시간이 상대적으로 오래 걸리게 됩니다. 따라서 동일한 페이지에 계속 있는다면, cache에서 반복적으로 접근하기 때문에 물리적으로 시간이 적게 들게 됩니다. 다시말해, 데이터의 이동이 적을수록 시간 측면에서 좋다는 것입니다.

 

Merge sort의 Locality

 

Merge sort는 기본적으로 끝과 끝을 계속 왔다 갔다 하면서 데이터를 탐색합니다. 또한, 내부적으로 해당 데이터들을 복사해야하기 때문에 시간이 더 오래걸립니다. 이는, cache의 페이지가 계속해서 바뀌기 때문에 locality의 효과가 떨어지게 됩니다.

 

Quick sort Locality

 

Quick sort의 경우에는 처음에 전체 탐색을 하면서 pivot을 기준으로 좌우로 나눕니다. 그 후, 좌우로 나눠서 재귀적으로 pivot을 기준으로 좌우를 나눕니다. 해당 과정을 반복하면 정렬이 끝납니다. 이는, 각 데이터들이 넓은 범위에서 움직이지 않는다는 것입니다. 다시 말해, cache의 페이지가 Merge sort에 비해 잘 바뀌지 않기 때문에 locality의 효과가 높아집니다. 

(= Quick sort는 하드웨어적으로 더 효율적인 정렬 방법입니다.)

 

결론

대부분의 프로그램들은 짧은 시간동안 반복적으로 접근하는 데이터들이 있습니다. 이 성질을 참조의 지역성이라고 합니다. 그래서 지역성을 띄는 데이터들을 더 빠르게 접근하기 위해서 cache라는 하드웨어를 이용합니다. 메인메모리보다 더 빨리 접근하기 위해서 만든 하드웨어입니다. 위에서 살펴 본 것과 같이, Quick sort는 Mergesort보다 더 참조의 지역성의 성질을 보입니다. 그래서 일반적으로 Quicksort이 더 빠른 것입니다.