quick sort vs. merge sort

https://stackoverflow.com/questions/9444714/how-is-quicksort-is-related-to-cache/9444866#9444866

How is quicksort is related to cache?

퀵 정렬은 in-place 정렬 입니다. in-place란 추가적인 공간을 요구하지 않고 주어진 배열 안에서 정렬을 시도한다는 것입니다. 이는 캐시를 사용하는데 있어서 '지역 참조성'이라는 이점을 얻을 수 있습니다.

메모리에 한 번 접근을 하면, 그 이후로는 캐시에만 접근하면 됩니다. 캐시는 속도 측면에서 RAM 메모리보다 훨씬 빠르기 때문에 연산 속도 이점을 얻을 수 있죠.

 

병합 정렬은 RAM에 더 많은 접근을 요구합니다. 왜냐하면 정렬을 할 때, 추가적인 배열을 만들어야 하기 때문입니다. 즉, in-place 정렬이 아니기 때문이죠. 병합 정렬은 공간 복잡도가 O(N)이라고 알려져 있습니다.

 

따라서 퀵 정렬은 병합 정렬보다 캐시로 이점을 더 많이 얻을 수 있다고 할 수 있습니다. 그런데 정렬해야 하는 데이터의 갯수가 상당히 많을 때는 퀵 정렬과 병합 정렬이 캐시로 이점을 얻을 수 있는게 비슷하지 않을까 하는 추측을 조심스럽게 해봅니다.

 

 

 

 

https://www.geeksforgeeks.org/quicksort-better-mergesort/

Why quicksort is better than mergesort ? - GeeksforGeeks

퀵 정렬이 병합 정렬보다 퍼포먼스 측면에서 최악 시간 복잡도(O(N^2) vs. O(NlogN)가 차이가 많이 남에도 불구하고, 왜 퀵 정렬이 병합 정렬보다 더 좋다고 할까요?

 

1. 추가적인 공간 : 병합 정렬은 추가적인 공간을 요구하는데 반해, 퀵 정렬은 in-place 정렬로 추가적인 공간을 요구하지 않습니다. 이는 캐시 이용을 높일 수 있습니다. (위에서 이미 설명하였음) 즉, 공간적 측면에서만 단점이 있는 것이 아니라, 이것이 캐시 이용적인 측면에서도 영향을 주기 때문에 속도에 까지 영향을 미친다고 할 수 있습니다.

 

2. 최악의 경우 : 퀵 정렬에서 가장 문제가 되는 것이 최악 케이스에서 입니다. 하지만 보통의 경우에는 이러한 케이스가 많지 않을 뿐만 아니라, pivot을 랜덤하게 잡는 방법으로 이 경우를 피할 수 있습니다. 만약, 10억개 숫자를 정렬해야 하고, 사이에 1억개가 정렬이 되어 있다면(?) 엄청나게 오래 걸릴 수 있습니다. 이런 경우가 없다고 할 수 없을 겁니다. 또한, 정렬이 되어 있다고 해도, 사람이 10억개를 다 볼 수가 없으므로 퀵 정렬을 한 번 시도해 볼 수도 있습니다. 최악의 경우가 많지 않다고도 말할 수가 없을 것 같네요.ㅎㅎㅎ 이런 경우를 피할 수 있게 퀵 정렬 변형 버전이 많이 있습니다.