건빵의 블로그

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로써 부가적인 공간을 필요로하지 않기 때문에 부가적인 공간에 제약이 있을 경우에는 merg..