Stable Sort 와 Unstable Sort 차이점

Leetcode를 풀다 보니, 속도가 빠른 답안들이 Sorting 을 할 때 그냥 vec.sort() 대신 아래와 같이 쓰고 있었습니다.

vec.sort_unstable();

찾아보니, 같은 값인 원소들의 상대적 순서를 처음과 동일하게 보존하는 것이 stable sort, 굳이 보존해 주지 않는 것이 unstable sort라고 합니다.

rust 공식 문서에 의하면 일부 예외를 제외하고 unstable sort가 더 빠르다고 합니다. 직관적으로도 그럴 것 같습니다. 오히려 예외가 있다는 게 신기합니다.

위키피디아에 검색해 보니, 각 sorting 알고리즘마다 stable 한지 아닌지 표시되어 있습니다.
그러면 좀 더 납득이 됩니다. Stable 한 특정 알고리즘이 가장 강한 case에서는 unstable 한 다른 알고리즘보다 빠를 수 있나 봅니다.

지금까지 sort()만 쓰고 있었는데 그렇게 사용한 대부분의 경우 원래 순서 보존이 필요 없었기 때문에, 앞으론 sort_unstable() 을 써보겠습니다.