자바에서 정렬을 수행할 때는 Integer, char과 같은 Primitive 원소에 대해서는 Dual-Pivot Quick Sort를 사용하고, 객체를 정렬할 때는 Tim Sort를 사용한다. (내부 함수 사용 시)
왜 객체와 객체가 아닌 것에 대해 따로 정렬을 수행할까?
한 가지 방법으로 통일하면 일관성을 유지할 수 있어 이해하기 쉽지 않을까?
이 질문에 대해 답하기 위해서는 In-place와 Stable여부를 알아야 한다.
정렬 알고리즘이 In-place하다면, 정렬 과정에서 정렬을 수행하는 N에 비해 무시할 만한 개수의 메모리만 사용함을 의미한다.
정렬할 요소의 수가 10만개이고, 10만개의 요소를 정렬할 때 추가로 사용해야하는 메모리가 10이라면 무시할 만 하다고 할 수 있다.
다음으로, 정렬 알고리즘이 Stable하다면 같은 위상의 원소들에 대해 원소들의 순서가 보존되는지를 의미한다.
2 3 4 4 1 을 오름차순으로 정렬한다고 하자. 1 2 3 4 4 가 결과로 나온다.
이 때, 처음 등장한 4와 나중에 등장한 4는 같은 위상을 가진다고 할 수 있다.
여기서 비교가 불가능한 두 대상에 대해 정렬이 끝난 후에도 입력된 순서가 유지된다면, 그 정렬 알고리즘은 Stable 하다고 할 수 있다.
Primitive원소를 정렬할 때는 In-place한 정렬 알고리즘인 Quick Sort를 사용하고, 객체를 정렬할 때는 Stable한 정렬 알고리즘인 Tim Sort를 사용한다.