컴퓨터는 왜 퀵소트를 주로 사용하는가?

전에 백승현 코치님이 말씀하신 퀵소트를 주로 쓰는 이유가 무엇인가? 에 대해
→ 퀵 정렬의 루프는 대부분 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있습니다. 메모리 참조가 지역화되어 있어 CPU 캐시의 히트율이 높아지기 때문입니다.

라고 답했다. 이걸로는 쉽게 이해하기 어려워 알기 쉽게 다시 알아봤다.

먼저, 퀵소트는 배열에서 작은 파티션으로 나누면서 정렬한다. 이 과정에서 서로 가까운 데이터만 다루면서 진행한다. 이 개념을 머리에 기억하자.

컴퓨터는 CPU라는 연산장치와 RAM이라는 임시저장소가 있다. 대게 CPU에서 계산하기위해서는 RAM에서 데이터를 끌어다가 계산한다. 이 과정에서 성능이 떨어진다. 그러나 CPU는 최근 계산한 내용이나 자주 사용하는 데이터를 “캐시”라는 작은 저장 공간에 저장해 둔다. 자주 사용하는 데이터는 RAM을 거칠 필요없이 계산 가능하다. 그러면 성능과 속도가 대폭 향상된다. 퀵소트는 위에서 말한 것과 같이 작은 파티션으로 나누어 가까운 데이터만 다루면서 진행하므로 RAM에서 데이터를 가져오는 느린 작업을 줄이고, CPU 속도에 가까운 빠른 속도로 정렬을 수행할 수 있다.
이를 우리는 메모리 참조의 지역성을 활용해서 CPU 캐시의 히트율을 높여 실행속도를 빠르게 할 수 있다고 한다. 그래서 주로 퀵소트를 많이 사용하게 된다.