같은 배열을 바꾸기
배열 안의 두 원소를 교환하며 순서를 바로잡는 방식은 원소를 다른 전체 배열로 옮기지 않아도 된다. 교환에 쓰는 임시 변수처럼 소량의 추가 저장은 사용할 수 있다. 입력을 수정한다는 점도 이용 시 고려해야 한다.
공간 정의의 범위
엄격하게 O(1) 보조 공간을 요구하는 설명도 있고 재귀의 관리 정보 등을 따로 허용하는 관례도 있다. 제자리라는 말 하나만 보고 추가 메모리가 전혀 없거나 모든 구현에서 상수라고 단정하지 않는다.
재귀 호출의 영향
퀵 정렬의 분할 처리는 같은 배열에서 할 수 있지만 재귀 호출은 별도의 스택 공간을 쓸 수 있다. 부분 문제의 크기와 호출 순서에 따라 그 공간이 달라진다. 원소를 담는 공간과 실행을 관리하는 공간을 함께 살펴야 한다.
안정성과 속도
제자리인지와 같은 키의 입력 순서를 보존하는지는 다른 성질이다. 또한 같은 공간을 재사용해도 실행 시간이 짧다는 보장은 없다. 정렬 방법을 비교할 때에는 공간, 시간, 안정성 요구를 각각 확인한다.
관련 문서
정렬 알고리즘 / 공간 복잡도 / 시간 복잡도 / 안정 정렬 / 퀵 정렬 / 힙 정렬 / 버블 정렬 / 재귀 / 배열 / 스택