재귀적인 정렬 알고리즘으로, 시간 복잡도가 나쁜 편에 속한다. 실행 시간이 버블 정렬보다는 느리지만, slow 정렬보다는 빠르다. 이름은 “The Three Stooges”라는 영화에서 유래되었다.
알고리즘은 다음과 같다.
첫 번째 요소와 마지막 요소를 비교한 뒤 첫 번째의 값이 더 큰 경우 두 요소를 서로 바꾼다.
그리고 목록에 3가지 이상의 요소가 존재할 경우, 다음의 세 과정을 거친다.
목록의 처음 2/3개의 요소에 대해 Stooge 정렬을 한다.
마지막 2/3개의 요소에 대해 Stooge 정렬을 한다.
처음 2/3개의 요소에 대해 다시 Stooge 정렬을 한다.
이때 요소 개수의 2/3를 올림으로 계산하여 정렬 크기를 지정한다는 것이 중요하다.
예를 들어 목록에 다섯 개의 요소가 있다고 할 때 5의 2/3은 3.3333… 이지만 3이 아니라 4로 계산한다.
아래는 Stooge 정렬의 swap 과정을 시각화한 것이다.
