나온 지 좀 된 글이니 조금 장난스럽게 얘기해 봐도 되겠음. 병합 정렬과 힙 정렬에는 나름의 아름다움이 있음. 이름만으로 핵심 아이디어를 알 수 있고, 동작 방식도 바로 드러남.
반면 퀵 정렬에는 그런 아름다움이 없고, 유일한 장점인 ‘많은 경우에 빠르다’는 특성을 이름으로 삼았음.

Hoare가 1960년에 분할 정렬이라고 이름 붙였다면, 기억에 잘 남지 않아 지금처럼 널리 퍼지고 인기를 얻지 못했을지도 모름.

퀵 정렬의 아름다움은 제자리 정렬이면서 놀라울 만큼 단순하다는 데 있음. 제자리 정렬이라는 특성을 활용하면 캐시 망각형 알고리즘에 매우 가깝게 만들 수 있음.

어떤 면에서 덜 아름다운 건가요? 진지하게 묻는 것이고, 아름답다는 기준이 무엇인지 궁금함.

실제 제목은 “Vectorized and performance-portable Quicksort” (2022) 임. 여기서 ‘최초’라는 표현의 정확한 의미는 다음과 같음.
최신 명령어 집합인 Arm SVE, RISC-V V, x86 AVX-512에는 분할에 적합한 compress-store 명령어가 있음. 각 원소가 피벗보다 작은지를 나타내는 참·거짓 값을 별도로 입력하면, 참에 해당하는 원소만 연속된 메모리에 저장함. 이 값을 논리적으로 반전해 같은 명령어를 다시 적용하면 나머지 원소를 다른 분할 영역에 쓸 수 있음. AVX-512 전용 퀵 정렬에서도 이 전략을 사용했으며, compress-store가 없는 AVX2 같은 명령어 집합에서는 순열 명령어로 이를 흉내 내는 방법이 기존 연구에 제시돼 있음.
이 기법들을 바탕으로 3개 아키텍처의 6개 명령어 집합에 이식 가능한 최초의 벡터화 퀵 정렬을 구현했으며, 기존 아키텍처 전용 정렬보다도 빠르다는 뜻임.

“Highway의 이식 가능한 SIMD 함수를 사용하므로 플랫폼마다 C++ 코드 약 3,000줄을 다시 구현할 필요가 없다”고 함.
지금도 같은 방식을 택할까, 아니면 LLM으로 C++ 3,000줄을 다시 구현할까?

적어도 5년은 된 사내 라이브러리가, LLM이 그 코드를 어설프게 되풀이해 만든 3,000줄보다 정확하고 성능도 좋을 가능성이 훨씬 높다고 봄.

언어 기능으로 코드를 재사용하던 시절을 다들 기억하시나요?

블로그의 9MB짜리 이미지 파일은 마음에 들지 않았음. 이미지가 완전히 표시되기까지 몇 초나 걸렸음.

2022년 글임. 숫자 목록을 벡터화해서 정렬할 이유가 궁금하다면, 활용처 중 하나는 히스토그램 생성임. 표본을 모두 먼저 정렬해 두면 히스토그램을 만들기가 훨씬 쉬워짐.

몇 년이 지난 지금, 어떤 애플리케이션에 이 방식이 구현됐는지 궁금함.

정렬 알고리즘을 보며 궁금했던 게 있음. 사람은 대개 값들이 얼마나 차이 나는지에 따라 수천 개 항목 중에서도 최솟값과 최댓값을 거의 즉시 눈으로 찾아낼 수 있음. AI도 시각적으로 최솟값과 최댓값을 찾게 할 수 있을까? 각 항목을 시각화해 가상의 벽에 펼쳐 놓고 AI가 ‘눈으로’ 골라내게 하는 방식은 어떨까?