평균적으로 퀵정렬(Quick Sort)이 왜 병합정렬(Merge Sort)보다 빠를까요?

[freakFlow]

답변

퀵정렬이 병합정렬보다 참조지역성이 더 좋기 때문입니다. 병합정렬의 경우, 좌우로 분할된 배열을 계속해서 움직이며 정렬하지만 퀵정렬의 경우, 피봇을 기준으로 좌우로 분할된 배열이 독립적으로 정렬을 하기때문에 참조지역성이 더 좋습니다.

[kimmainsain]

답변

• 퀵정렬은 참조지역성의 특징으로 인해, 병합정렬보다 빠른 것으로 알고 있습니다.
• 병합 정렬은 추가 저장 공간이 필요하기 때문에, 공간 할당과 해제에 시간이 소모됩니다.