한 개발자가 호기심으로 만든 'MinMAX 정렬(MinMAX Sort)' 알고리즘이 기존 선택 정렬(Selection Sort)의 효율성을 크게 개선하며 주목받고 있습니다. 이 알고리즘은 전통적인 선택 정렬과 동일하게 O(n^2)의 시간 복잡도를 가지지만, 연산 횟수를 절반으로 줄여 실제 성능을 향상시켰습니다. 이는 외부 루프(outer loop)와 내부 루프(inner loop)의 연산 횟수를 각각 n/2와 (n x n)/2만큼 감소시킨 결과입니다.
MinMAX 정렬은 양방향 탐색(bidirectional search) 방식을 채택하여 배열의 최소값과 최대값을 동시에 찾아 정렬합니다. 이러한 접근 방식은 '안정적인(stable)' 정렬 알고리즘의 특성을 유지하면서도, 기존 선택 정렬이 한 번의 루프에서 하나의 원소만 제자리에 놓는 비효율성을 개선합니다. 개발자는 이 알고리즘이 '절벽(cliff)', '스파이크(spike)', '역순(reverse)', '중복(duplicates)' 등 다양한 형태의 배열에서 안정적으로 작동함을 여러 테스트를 통해 검증했습니다.
이러한 개선은 이론적으로는 여전히 O(n^2) 복잡도를 가지지만, 실제 환경에서의 성능 향상을 가져올 수 있다는 점에서 의미가 있습니다. 특히 교육용이나 특정 데이터셋에서는 기존 선택 정렬보다 더 나은 선택지가 될 수 있습니다. 이는 컴퓨터 과학(CS) 분야에서 오래된 알고리즘도 새로운 관점으로 접근하여 개선의 여지가 있음을 보여주는 사례로, 학계와 개발 커뮤니티에 신선한 자극을 줄 것으로 기대됩니다.