[Algorithms] stable sort와 unstable sort(Merge vs Quick)

sort를 나타낼 때 stability로 구분하기도 하는데요.

stable sort의 의미는 정렬 후에도 정렬된 순서가 그대로 유지되는 것을 말하며
unstable sort는 stable하지 않은 것을 의미합니다.

stable sort 중 대표적인 것이 Merge sort이며
unstable sort 중 대표적인 것이 Quick sort입니다.

두 sort 다 average case의 경우에는 n lg n의 order를 가지지만
안정성에서 Merge가 낫고 또한 worst의 경우에도 Merge는 n lg n이므로 Merge를 사용하는게 더 낫다고 볼 수 있습니다.
하지만 Quick sort는 in-place sort로써 부가적인 공간을 필요로하지 않기 때문에 부가적인 공간에 제약이 있을 경우에는
merge sort보다는 Quick sort를 사용하는 것이 나을 것입니다.